algoadvance

Leetcode 1608. Special Array With X Elements Greater Than or Equal X

Problem Statement

You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x. Notice that x does not have to be an element in nums.

Return x if the array is special, otherwise return -1.

Clarifying Questions

  1. What is the size range of the nums array?
    • The array length can vary from 0 to 100.
  2. What can be the values of elements in nums?
    • Each element in nums is a non-negative integer from 0 to 100.
  3. Can the array be empty?
    • Yes, the array can be empty. In this case, the output should be -1.

Strategy

To solve this problem, you can use the following steps:

  1. Sort the Array: Sorting helps in counting elements efficiently.
  2. Iterate and Validate: Iterate from 0 to the length of the array. For each index, check if the condition for special number x is satisfied.
  3. Return the Result: If such a number x is found, return it; otherwise, return -1.

Code

Here is the implementation in Java:

import java.util.Arrays;

public class SpecialArray {
    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;

        for (int x = 0; x <= n; x++) {
            int count = 0;
            for (int num : nums) {
                if (num >= x) {
                    count++;
                }
            }
            if (count == x) {
                return x;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        SpecialArray solution = new SpecialArray();
        int[] nums1 = {3, 5};
        int result1 = solution.specialArray(nums1);
        System.out.println(result1);  // Output: 2

        int[] nums2 = {0, 0};
        int result2 = solution.specialArray(nums2);
        System.out.println(result2);  // Output: -1

        int[] nums3 = {0, 4, 3, 0, 4};
        int result3 = solution.specialArray(nums3);
        System.out.println(result3);  // Output: 3
        
        int[] nums4 = {3,6,7,7,0};
        int result4 = solution.specialArray(nums4);
        System.out.println(result4);  // Output: -1
    }
}

Time Complexity

  1. Sorting: The array is sorted initially which takes O(n log n) time.
  2. Iteration and Validation: We iterate over the array to calculate the count, which takes O(n) time and is done O(n) times in the worst case.

Overall, the time complexity is O(n log n) due to the sorting step being the most time-consuming part.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI