Leetcode needs to hire a new staff for question description :D

@supremoluminary

Ай бұрын

Pointless weird questions, badly worded! It is work to accomplish nothing other than being able to pass interviews. It's not practicable or reusable knowledge.

Hey Neetcode, Thanks to you. I got a job at Goldman Sachs because of your videos.

Probably more messy solution in C++, but still passing all the tests: int specialArray(vector& nums) { nums.push_back(-1); sort(nums.begin(), nums.end()); int cnt = 0, j = nums.size() - 1; while (j > 0) { while (j - 1 >= 0 and nums[j - 1] == nums[j]) j--, cnt++; j--, cnt++; if (cnt > nums[j] and cnt

is there a need for the extra while loop at 11:20 as the we can combine the condition in the outer while loop as prev

you made the sorting solution more complicated than it need to: function specialArray(nums: number[]): number { nums.sort((a, b) => a - b); for (let i = 0; i const n = nums.length - i; if (nums[i] >= n && (i === 0 || n > nums[i - 1])) return n; } return -1; };

@ExploraByte

Ай бұрын

nums.sort() n = len(nums) prv = -1 for i in range(n): if nums[i] >= n - i and n - i > prv: return n - i prv = nums[i] return -1

Hey could you show the contest problem and solutions

thanks for solution

Nice🎉

This problem is same as H-index problem (274 H-Index) , really hard to understand/code but good for binary search understanding and practice. Multiple solutions from O(n*n) to O(n*logn + n*logn) then O(n*logn + logn * logn) and finally O(n) solution using bucket sort.

18:49 in the second loop , if you are doing the traditional way -> for i in range(len(nums)-1, -1, -1): Then this would be wrong as it would exclude the value at count[len(nums)] as possible answer So instead you need to right the range as -> for i in range(len(nums), -1, -1):

@NeetCodeIO

Ай бұрын

yeah you're right, good catch!

I used binary search on 1 to the length of the array to find x I believe it's also N log N

@shiveshkumar1965

Ай бұрын

can you send your solution?

@shaypatrickcormac2765

Ай бұрын

that is N log(M) with M is the maximum

@ritikaagrawal769

Ай бұрын

yeah that's nlogn, I was wondering if i was the only one who's first intuition was binary search.

@ritikaagrawal769

Ай бұрын

@@shiveshkumar1965 Here, hope this helps. def specialArray(self, nums: List[int]) -> int: l = 1 #we know 0 can never be the answer, so we start with 1 r = len(nums) #maximum answer can be n while l = m : count+=1 #if count is less, our m is too big, and vice versa. if count r = m-1 elif count > m : l = m+1 else: return m return -1 Overall time complexity - O(n*logn)

@mohamedzaheen3246

Ай бұрын

@@shiveshkumar1965 class Solution { public: int count(vector& nums, int num, int n) { int cnt = 0; for (int i = 0; i if (nums[i] >= num) cnt++; } return cnt; } int specialArray(vector& nums) { int n = nums.size(); int l = 0; int r = n; while (l

19:36 We can "return i" instead of "return -1 " also since i becomes -1 at the end of the for loop anyways? I know this becomes more confusing

What is a Prefix Array? I have not comprehended either explanation yet.

@supremoluminary

Ай бұрын

A Prefix Array, also known as a Prefix Sum Array or Cumulative Sum Array, is an Array with the calculation of cumulative sums of elements in a source array. It stores the cumulative sum of elements up to a certain index in the array. This can also be done in-place, so that the target rewrites values of the source. Here's how it works: Given an array of numbers, the prefix array would be another array where each element prefix[i] stores the sum of elements from index 0 to index i in the array. For example, if the original array is [1, 2, 3, 4, 5], the prefix array would be [1, 3, 6, 10, 15], because: prefix[0] = 1 (sum of elements from index 0 to index 0) prefix[1] = 1 + 2 = 3 (sum of elements from index 0 to index 1) prefix[2] = 1 + 2 + 3 = 6 (sum of elements from index 0 to index 2) prefix[3] = 1 + 2 + 3 + 4 = 10 (sum of elements from index 0 to index 3) prefix[4] = 1 + 2 + 3 + 4 + 5 = 15 (sum of elements from index 0 to index 4) Huh.

@supremoluminary

Ай бұрын

Here is an example of a prefix array in JavaScript:- const nums = [1, 2, 3, 4, 5]; nums.forEach((num, i) => nums[i] += nums[i-1] ?? 0); - but I'm still fuzzy on the reverse array. I think you want like a suffix array, not a reverse prefix array. So, for example, if the array is [1, 2, 3, 4, 5], the suffix array would be:- suffix[4] = 5 suffix[3] = 5 + 4 = 9 suffix[2] = 5 + 4 + 3 = 12 suffix[1] = 5 + 4 + 3 + 2 = 14 suffix[0] = 5 + 4 + 3 + 2 + 1 = 15 - [15, 14, 12, 9, 5] Did I get that right?

@supremoluminary

Ай бұрын

function createSuffixArray(nums) { const suffixArray = new Uint32Array(nums.length); for (let i = nums.length - 1, sum = 0; i >= 0; i--) { sum += nums[i]; suffixArray[i] = sum; } return suffixArray; } const nums = [1, 2, 3, 4, 5]; createSuffixArray(nums); [15, 14, 12, 9, 5] Whew.

with those limits provided - array is only 1000 elements at max - any bruteforce generally is pareto optimal. any neat tricks to skip couple elements, or stop checking and continue next loop will be mitigated with other unskippable sequences.

I don't understand the second solution with count

Sorting + Binary Search solution. I guess this should be bit more efficient than Sorting + Linear Search. class Solution { public int specialArray(int[] nums) { int len = nums.length; Arrays.sort(nums); for (int num = 1; num = num && (len - posSt) == num) return len - posSt; } return -1; } private int isValid(int[] nums, int el) { int low = 0, high = nums.length - 1; while (low

not understand

I think you messed up explaining the second part ( the case where we have duplicate elements). It is not clear :(

@zanies6288

Ай бұрын

Just do binary for x in the range 1 to N

The linear time solution is a little difficult to understand

@alexguo7343

Ай бұрын

who can come up with this solution the first time they see it? not me for sure!

very easy using sorting but prolly a medium with the counting approach tbh

class Solution: def specialArray(self, nums: List[int]) -> int: nums.sort() n = len(nums) prev = -1 for i, num in enumerate(nums): if prev < n-i

@yelnil

Ай бұрын

This is O(n logn) because of sort(). Using bucket sort like in the video makes it O(n)

This question is horribly phrased. I cant seem to understand this at all.

I'm stupid

I think this is the first time your easy solution isn't too comprehendible. I think you would've been better explaining the first solution O(nlogn) with Binary Search imo; still love your content anyway.