Smallest Index With Equal Value

EASY

Description

Given a 0-indexed integer array nums, return the smallest index i of nums such that i mod 10 == nums[i], or -1 if such index does not exist.

x mod y denotes the remainder when x is divided by y.

Example 1:

Input: nums = [0,1,2]
Output: 0
Explanation: 
i=0: 0 mod 10 = 0 == nums[0].
i=1: 1 mod 10 = 1 == nums[1].
i=2: 2 mod 10 = 2 == nums[2].
All indices have i mod 10 == nums[i], so we return the smallest index 0.

Example 2:

Input: nums = [4,3,2,1]
Output: 2
Explanation: 
i=0: 0 mod 10 = 0 != nums[0].
i=1: 1 mod 10 = 1 != nums[1].
i=2: 2 mod 10 = 2 == nums[2].
i=3: 3 mod 10 = 3 != nums[3].
2 is the only index which has i mod 10 == nums[i].

Example 3:

Input: nums = [1,2,3,4,5,6,7,8,9,0]
Output: -1
Explanation: No index satisfies i mod 10 == nums[i].

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 9

Approaches

Checkout 2 different approaches to solve Smallest Index With Equal Value. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Search with Extra Storage

This approach involves a full scan of the array to identify all indices i that satisfy the condition i mod 10 == nums[i]. These valid indices are collected in a separate list. After the scan is complete, if the list contains any indices, the smallest one is returned. If the list is empty, it signifies that no such index exists, and -1 is returned.

Algorithm

Initialize an empty list, for example, validIndices, to store the indices that satisfy the condition.
Iterate through the input array nums from index i = 0 to nums.length - 1.
Inside the loop, for each index i, check if i % 10 == nums[i].
If the condition holds true, add the index i to the validIndices list.
After the loop finishes, check if the validIndices list is empty.
If it is empty, return -1.
Otherwise, return the first element of validIndices, which is guaranteed to be the smallest since we added indices in increasing order.

Algorithm:

Initialize an empty list, for example, validIndices, to store the indices that satisfy the condition.
Iterate through the input array nums from index i = 0 to nums.length - 1.
Inside the loop, for each index i, check if i % 10 == nums[i].
If the condition holds true, add the index i to the validIndices list.
After the loop finishes, check if the validIndices list is empty.
If it is empty, return -1.
Otherwise, return the first element of validIndices, which is guaranteed to be the smallest since we added indices in increasing order.

Code Snippet:

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int smallestEqual(int[] nums) {
        List<Integer> validIndices = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i % 10 == nums[i]) {
                validIndices.add(i);
            }
        }

        if (validIndices.isEmpty()) {
            return -1;
        } else {
            return validIndices.get(0);
        }
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the number of elements in the `nums` array. The entire array is traversed once.Space Complexity: O(K), where K is the number of indices satisfying the condition. In the worst-case scenario (e.g., `nums = [0, 1, 2, ...]`), K can be equal to N, leading to O(N) space complexity.

Pros and Cons

Pros:

The logic is straightforward and easy to follow.
It correctly identifies all possible solutions before selecting the smallest one.

Cons:

Uses extra space to store valid indices, which is not optimal.
It always iterates through the entire array, even if the smallest valid index is found at the beginning.

Code Solutions

Checking out 3 solutions in different languages for Smallest Index With Equal Value. Click on different languages to view the code.

class Solution {
public
  int smallestEqual(int[] nums) {
    for (int i = 0; i < nums.length; ++i) {
      if (i % 10 == nums[i]) {
        return i;
      }
    }
    return -1;
  }
}

Video Solution

Watch the video walkthrough for Smallest Index With Equal Value

Data Structures:

Array