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

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

Рет қаралды 11,232

NeetCodeIO

Күн бұрын

Пікірлер: 40

@tarun4705 5 ай бұрын

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

@luuduytoan3819 5 ай бұрын

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

@supremoluminary 5 ай бұрын

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 5 ай бұрын

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

@zero180795 5 ай бұрын

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 5 ай бұрын

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

@kanishkkala16 5 ай бұрын

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 5 ай бұрын

yeah you're right, good catch!

@nirmalgurjar8181 5 ай бұрын

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.

@13Blu 5 ай бұрын

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

@shiveshkumar1965 5 ай бұрын

can you send your solution?

@shaypatrickcormac2765 5 ай бұрын

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

@ritikaagrawal769 5 ай бұрын

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

@ritikaagrawal769 5 ай бұрын

@@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 5 ай бұрын

@@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 5 ай бұрын

Hey could you show the contest problem and solutions

@shriharinair1999 5 ай бұрын

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 5 ай бұрын

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.

@satyam2312 5 ай бұрын

thanks for solution

@JRK_RIDES 5 ай бұрын

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

@tekfoonlim4745 5 ай бұрын

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

@flavorfabs 5 ай бұрын

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.

@kahafb 5 ай бұрын

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 5 ай бұрын

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

@supremoluminary 5 ай бұрын

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

@supremoluminary 5 ай бұрын

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 5 ай бұрын

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 5 ай бұрын

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.