Sponsored
Sponsored
Sort the array first. For each possible count of elements x, check if there are exactly x numbers in the array that are greater than or equal to x.
Time Complexity: O(n log n) due to sorting, followed by O(n) for checking, resulting in O(n log n). Space Complexity: O(1) additional space.
1import java.util.Arrays;
2
3public class SpecialArray {
4 public int specialArray(int[] nums) {
5 Arrays.sort(nums);
6 int n = nums.length;
7 for (int x = 0; x <= n; x++) {
8 int count = 0;
9 for (int num : nums) {
10 if (num >= x) {
11 count++;
12 }
13 }
14 if (count == x) {
15 return x;
16 }
17 }
18 return -1;
19 }
20 public static void main(String[] args) {
21 SpecialArray sa = new SpecialArray();
22 int[] nums = {0, 4, 3, 0, 4};
23 System.out.println(sa.specialArray(nums));
24 }
25}
This Java solution sorts the array and iteratively checks the count of values greater than or equal to each x.
Utilize binary search on the result potential values from 0 to nums.length to efficiently find the special x.
Time Complexity: O(n log n) due to sorting initially, and O(n log n) for the binary search with counting operations. Space Complexity: O(1) additional space.
1
This solution uses binary search over the number of potential special cases, reducing the search space for efficiency.