Smallest Index With Equal Value
EasyPrompt
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 <= 1000 <= nums[i] <= 9
Approaches
2 approaches with complexity analysis and trade-offs.
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
numsfrom indexi = 0tonums.length - 1. - Inside the loop, for each index
i, check ifi % 10 == nums[i]. - If the condition holds true, add the index
ito thevalidIndiceslist. - After the loop finishes, check if the
validIndiceslist 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.
Walkthrough
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
numsfrom indexi = 0tonums.length - 1. - Inside the loop, for each index
i, check ifi % 10 == nums[i]. - If the condition holds true, add the index
ito thevalidIndiceslist. - After the loop finishes, check if the
validIndiceslist 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
Time
O(N), where N is the number of elements in the `nums` array. The entire array is traversed once.
Space
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.
Trade-offs
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.
Solutions
Solution
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 walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.