Prime Subtraction Operation - Leetcode 2601 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
7:25 - Coding Explanation
12:55 - Coding Explanation 2

leetcode 2601

#neetcode #leetcode #python

[treelibrarian]

I found it more logical to scan the array in reverse since the last element of the array is the fixed point to work back from ... but otherwise basically the same approach.
I can also imagine a meta-optimization where the primes array can be reused and extended if needed between testcases, since they are the most work but don't change, but it's hard to know how the testing is done and if the memory can be preserved between testcases or not... all I know is that I have had failures where globals didn't get reset between tests in the past, but then sometimes they are as well?

[SergeyAngelov]

If we take into account constraints, we can prebuild sieve of Eratosthenes and then use binary search approach to get the closest prime.

[pradeeppradhi]

how can we come up with these kind of ideas? i am able to normal brute force but struggling to come up for optimized one,

[anonanon]

You should give us constrains when stating the problem.
It helps to discard many potential ways of thinking from the get go.

On the other hand it might be me who's too reliant on them.

[TrevorDove-lfot]

I don't get why we only subtract the largest possible prime. Couldn't there be a test case where you'd need to subtract the second-largest prime at some point in the list?

[aashishbathe]

Optimization using Sieve of Eratosthenes??
P.S - Haven't watched the complete video yet!

[MP-nyep]

Great explanation as always.Thank you !

[akakop]

Hi neetcode, what is the macbook config you have? Which you use for your YouTube business.

[Aaron-cptt]

I have a bit of confusion about 'upper_bound.' Can this value be negative, and how should I deal with it? Does it affect the index of the primes array?

[gauravmandal]

Sieve of Eratosthenes is Very standard Algorithm for precomputing Prime Numbers

[leesinisbae]

When it was clear that we had lower/upper bound, couldn't we think of binary search too?

[sujjjju]

what software do you use for the highlighting?

[realAhmedAbdElGhany]

Why would we stop at the square root of the number ?

[ajitpalsingh]

Can we use binary search?

int bs(int num, vector<int>& nums, int i) {
int low = 2, high = num-1, ans;
while (low <= high) {
int mid = (low + high) / 2;
if (check(mid) && (i == 0 || (nums[i] - mid) > nums[i - 1])) {
return mid;
} else if (i == 0 || (nums[i] - mid) < nums[i - 1]) {
high = mid - 1;
} else {
low = mid + 1;
}
if(check(mid))
ans = mid;
}
return ans;
}

[arihantsinghrana]

@NeetCodeIO why in Java am I getting -1 index out of bound error ??
error : Index -1 out of bounds for length 9
Please help !! I had written the same code as you have !

[CourierSix]

This problem took me total 15 hour still can't figure out where am I stuck. 😢

I dont want to see the solution...
But i dont want to waste the time...

[-ArnobBiswas]

My submission is pending on leetcode for an hour now. It just shows pending and doesn't give any verdict. Anyone else facing this?

[dharsha-gv]

Neetcode while going to school is codexusally arousing!