algoadvance

Leetcode 2784. Check if Array is Good

Problem Statement

  1. Check if Array is Good

You are given an array nums of length n consisting of distinct integers from the range [0, n-1].

A “good” array is defined as an array where:

  1. Each integer from the range [0, n-1] appears exactly once in the array.

Write a function isGoodArray(int[] nums) that returns true if the array is “good” and false otherwise.

Example:

Input: nums = [3, 0, 1, 2]
Output: true

Input: nums = [1, 2, 3, 4]
Output: false

Clarifying Questions

  1. Can the array contain negative numbers?
    • No, according to the problem statement, the integers are from the range [0, n-1].
  2. What is the size of the array?
    • The length of the array is n.
  3. Can there be duplicate numbers in the array?
    • No, all integers are distinct as per the problem statement.

Strategy

To solve this problem, the approach is straightforward since the array contains distinct integers, and we just need to check if every integer from 0 to n-1 is present in the array. Here’s how we can do this:

  1. Sort the array and check if it matches the sequence [0, 1, 2, ... , n-1].
  2. Use a HashSet to add each element in the array and then check if the size of the HashSet is n and it contains all integers from 0 to n-1.

I will use the second approach which doesn’t involve sorting and is efficient.

Code

import java.util.HashSet;

public class Solution {
    public boolean isGoodArray(int[] nums) {
        int n = nums.length;
        HashSet<Integer> set = new HashSet<>();

        for (int num : nums) {
            set.add(num);
        }

        if (set.size() != n) {
            return false;
        }

        for (int i = 0; i < n; i++) {
            if (!set.contains(i)) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {3, 0, 1, 2};
        int[] nums2 = {1, 2, 3, 4};
        System.out.println(solution.isGoodArray(nums1)); // Output: true
        System.out.println(solution.isGoodArray(nums2)); // Output: false
    }
}

Time Complexity

This solution efficiently checks if the array contains all numbers from 0 to n-1 exactly once.

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