Find All Good Indices - Leetcode Solution

Problem Statement:

You are given an array nums containing n integers.

A maximum integer is called a good index if it has the property that all elements to its left are strictly smaller than it.

Return an array of all the good indices of the array nums.

Solution:

To solve this problem, we can iterate through the given array from left to right and keep a track of the maximum value of all the elements seen so far. If an element is greater than the maximum value seen so far, it is a good index. We can store the good indices in a separate array and return it.

Algorithm:

1. Initialize an empty array goodIndices to store the good indices.
2. Initialize a variable max_value to -inf (negative infinity).
3. Iterate through the given array nums from left to right: a. If the current element is greater than the max_value: i. Append the index of the current element to the goodIndices array. ii. Update max_value to the current element.
4. Return the goodIndices array.

Code:

Here is the Python code for the above algorithm:

class Solution: def findGoodIndices(self, nums: List[int]) -> List[int]:

    goodIndices = []
    max_value = float('-inf')
    
    for i in range(len(nums)):
        if nums[i] > max_value:
            goodIndices.append(i)
            max_value = nums[i]
            
    return goodIndices

Time Complexity:

The above algorithm has a time complexity of O(n), where n is the length of the given array nums.

Space Complexity:

The above algorithm has a space complexity of O(k), where k is the number of good indices in the given array nums. In the worst case, all the elements of the given array nums can be good indices, giving us a space complexity of O(n).

1