Special Array with X Elements Greater than or Equal X - Leetcode 1608 - Python

[@tarun4705]

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

[@luuduytoan3819]

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.

[@speedie3284]

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

[@kanishkkala16]

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!

[@zero180795]

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 < nums.length; 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

[@13Blu]

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 < m : 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 < n; i++) { if (nums[i] >= num) cnt++; } return cnt; } int specialArray(vector& nums) { int n = nums.size(); int l = 0; int r = n; while (l

[@saranshthukral4021]

Hey could you show the contest problem and solutions

[@nirmalgurjar8181]

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.

[@supremoluminary]

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.

[@shriharinair1999]

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

[@DeathSugar]

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.

[@tekfoonlim4745]

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

[@Aryan-ji2nk]

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

[@Antinormanisto]

I don't understand the second solution with count

[@satyam2312]

thanks for solution

[@JRK_RIDES]

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

[@flavorfabs]

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.

[@codeguru4]

not understand

[@chien-yuyeh9386]

Nice🎉

[@rasik7649]

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!

[@kahafb]

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

[@yelgabs]

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

[@bst-vf5su]

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

[@greatfate]

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

[@deathbombs]

I'm stupid