algoadvance

Leetcode 2784. Check if Array is Good

Problem Statement

The problem “Check if Array is Good” typically presents an array of integers and asks you to determine if the array meets certain conditions to be classified as “Good”. While the specific conditions aren’t provided directly here, such problems generally follow a pattern that can be deduced from the context or past experiences. For this exercise, we will assume the following conditions for an array to be “Good”:

  1. All elements in the array are distinct.
  2. The elements are in non-decreasing order.
  3. The array contains all integers from 1 up to its length.

Given these conditions, we will implement a function to check if the given array meets these criteria.

Clarifying Questions

Before we approach the solution, let’s clarify a few key points:

  1. Are the values in the array guaranteed to be positive integers?
    • Yes.
  2. Is there a specific range for the array length?
    • We assume the array length can be any non-negative integer.

Strategy

To determine if the array is “Good”, we will follow these steps:

  1. Check if all elements in the array are unique.
  2. Check if the array is sorted in non-decreasing order.
  3. Check if the array contains all integers from 1 up to its length.

We will implement separate checks and combine the results.

Code

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

bool isArrayGood(const std::vector<int>& arr) {
    int n = arr.size();
    if (n == 0) return false;
    
    // Step 1: Check if all elements are distinct
    std::unordered_set<int> seen;
    for (int num : arr) {
        if (seen.find(num) != seen.end()) return false;
        seen.insert(num);
    }
    
    // Step 2: Check if the array is in non-decreasing order
    for (int i = 1; i < n; ++i) {
        if (arr[i] < arr[i - 1]) return false;
    }
    
    // Step 3: Check if the array contains all integers from 1 to n
    for (int i = 1; i <= n; ++i) {
        if (std::find(arr.begin(), arr.end(), i) == arr.end()) return false;
    }
    
    return true;
}

int main() {
    std::vector<int> arr1 = {1, 2, 3, 4, 5}; // Good
    std::vector<int> arr2 = {1, 2, 2, 4, 5}; // Not Good (duplicate 2)
    std::vector<int> arr3 = {1, 2, 3, 5, 4}; // Not Good (not sorted)
    std::vector<int> arr4 = {1, 2, 3, 5};    // Not Good (missing 4)
    
    std::cout << std::boolalpha << isArrayGood(arr1) << std::endl; // true
    std::cout << std::boolalpha << isArrayGood(arr2) << std::endl; // false
    std::cout << std::boolalpha << isArrayGood(arr3) << std::endl; // false
    std::cout << std::boolalpha << isArrayGood(arr4) << std::endl; // false
    
    return 0;
}

Time Complexity

The time complexity for this solution is determined by the following steps:

  1. Checking for distinct elements: O(n)
  2. Checking for non-decreasing order: O(n)
  3. Checking for completeness from 1 to n: O(n^2), due to the nested loop with std::find

The overall time complexity is dominated by the O(n^2) step. This can be reduced to O(n) if we use an additional data structure (like a boolean array) to check for completeness in linear time.

bool isArrayGood(const std::vector<int>& arr) {
    int n = arr.size();
    if (n == 0) return false;
    
    // Step 1: Check if all elements are distinct and between 1 and n
    std::unordered_set<int> seen;
    for (int num : arr) {
        if (num < 1 || num > n || seen.find(num) != seen.end()) return false;
        seen.insert(num);
    }
    
    // Step 2: Check if the array is in non-decreasing order
    for (int i = 1; i < n; ++i) {
        if (arr[i] < arr[i - 1]) return false;
    }
    
    return true;
}

In this revised code, we have an overall time complexity of O(n), making it more efficient.

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