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

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.

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

yeah you're right, good catch!

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

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.

Just do binary for x in the range 1 to N

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

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