Special Array with X Elements Greater than or Equal X - Leetcode 1608 - Python
ฝัง
- เผยแพร่เมื่อ 22 ก.ค. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/special...
0:00 - Read the problem
0:30 - Intuition
3:05 - Sorting Explanation
7:55 - Coding Sorting
12:19 - Counting Explanation
16:53 - Coding Counting
leetcode 1608
#neetcode #leetcode #python
Leetcode needs to hire a new staff for question description :D
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 < nums.length; i++) {
const n = nums.length - i;
if (nums[i] >= n && (i === 0 || n > nums[i - 1])) return n;
}
return -1;
};
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
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):
yeah you're right, good catch!
thanks for solution
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.
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
I used binary search on 1 to the length of the array to find x I believe it's also N log N
can you send your solution?
that is N log(M) with M is the maximum
yeah that's nlogn, I was wondering if i was the only one who's first intuition was binary search.
@@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)
@@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
I don't understand the second solution with count
Nice🎉
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.
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.
What is a Prefix Array?
I have not comprehended either explanation yet.
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.
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?
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.
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
The linear time solution is a little difficult to understand
who can come up with this solution the first time they see it? not me for sure!
I think you messed up explaining the second part ( the case where we have duplicate elements). It is not clear :(
Just do binary for x in the range 1 to N
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
This is O(n logn) because of sort(). Using bucket sort like in the video makes it O(n)
very easy using sorting but prolly a medium with the counting approach tbh
This question is horribly phrased. I cant seem to understand this at all.
I'm stupid