LeetCode Entry
1608. Special Array With X Elements Greater Than or Equal X
Count of more or equal nums[i] equal itself
1608. Special Array With X Elements Greater Than or Equal X easy
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/619
Problem TLDR
Count of more or equal nums[i] equal itself #easy
Intuition
Star with brute force, the n is in range 0..1000, try them all, and for each count how many numbers are nums[i] >= n.
This will pass the checker.
Now time to optimize. If we sort the nums we can optimize the nums[i] >= n, as n only grows up so the i. We can start with the previous i next time.
Another optimizations, there are no more than nums.size count possible, so n’s range is 0..nums.size inclusive.
Approach
Let’s write non-optimal one-liner in Kotlin, and more robust solution in Rust.
Complexity
-
Time complexity: \(O(nlogn)\) and \(O(n^2)\)
-
Space complexity: \(O(1)\)
Code
fun specialArray(nums: IntArray): Int = (0..nums.size)
.firstOrNull { n -> n == nums.count { it >= n }} ?: -1
pub fn special_array(mut nums: Vec<i32>) -> i32 {
nums.sort_unstable(); let (mut n, mut i) = (0, 0);
for n in 0..=nums.len() {
while i < nums.len() && nums[i] < n as i32 { i += 1 }
if n == nums.len() - i { return n as i32 }
}; -1
}