LeetCode 2057 - Smallest Index With Equal Value
The problem gives us a 0-indexed integer array nums. We must find the smallest index i such that: The expression i mod 10 means the remainder when i is divided by 10. We are asked to scan the array and determine whether any index satisfies this condition.
Difficulty: 🟢 Easy
Topics: Array
Solution
Problem Understanding
The problem gives us a 0-indexed integer array nums. We must find the smallest index i such that:
$$i \bmod 10 = nums[i]$$
The expression i mod 10 means the remainder when i is divided by 10.
We are asked to scan the array and determine whether any index satisfies this condition. If multiple indices satisfy it, we must return the smallest one. If no index satisfies the condition, we return -1.
The input array contains integers between 0 and 9, inclusive. The array length is at most 100, so the input size is very small. This immediately suggests that a simple linear scan is more than sufficient.
For example, consider:
nums = [4,3,2,1]
We check each index:
0 % 10 = 0, not equal to41 % 10 = 1, not equal to32 % 10 = 2, equal to2
Since index 2 is the first valid index, we return 2.
The important detail is that we must return the smallest valid index. That means the moment we find a matching index during a left-to-right traversal, we can stop immediately.
The constraints also guarantee:
- The array always has at least one element.
- Every value is already within
0to9. - The array is small enough that even inefficient approaches would pass.
Important edge cases include:
- Arrays where the first index already satisfies the condition.
- Arrays where no index satisfies the condition.
- Arrays with multiple valid indices, where we must return the smallest one.
- Arrays longer than
10, because indices larger than9wrap around under modulo10.
Approaches
Brute Force Approach
The brute force solution is straightforward. We iterate through every index i in the array and compute i % 10. We then compare that value with nums[i].
If they match, we immediately return i because we are scanning from left to right, so the first match is automatically the smallest valid index.
If we finish scanning the entire array without finding a match, we return -1.
This approach is guaranteed to work because it explicitly checks every possible candidate index.
Although this is called a brute force approach, it is already efficient enough because the array size is at most 100.
Optimal Approach
The optimal approach is actually the same linear scan strategy.
The key observation is that the problem only requires checking each index independently. There is no need for additional data structures, preprocessing, sorting, or dynamic programming.
Because we only need the first valid index, we can stop immediately once we find a match. This gives us an efficient single-pass solution.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Checks every index one by one |
| Optimal | O(n) | O(1) | Same linear scan, exits early on first match |
Algorithm Walkthrough
- Start iterating through the array from index
0. - For each index
i, compute the remainderi % 10. - Compare the computed value with
nums[i]. - If they are equal, immediately return
i.
This works because we are scanning from left to right, so the first match is guaranteed to be the smallest valid index.
5. If the loop finishes without finding any valid index, return -1.
Why it works
The algorithm works because it checks every possible index exactly once. Since the traversal order is from smallest index to largest index, the first matching index encountered must be the smallest valid answer. If no index satisfies the condition, returning -1 is correct because every candidate has already been tested.
Python Solution
from typing import List
class Solution:
def smallestEqual(self, nums: List[int]) -> int:
for index, value in enumerate(nums):
if index % 10 == value:
return index
return -1
The solution uses Python's enumerate() function to iterate through both the index and value simultaneously.
For each position:
index % 10computes the remainder of the index divided by10- The result is compared with the current array value
If they match, the function immediately returns the current index because it is the smallest valid one encountered so far.
If the loop completes without returning, no valid index exists, so the function returns -1.
The implementation directly mirrors the algorithm described earlier and uses only constant extra space.
Go Solution
func smallestEqual(nums []int) int {
for index, value := range nums {
if index%10 == value {
return index
}
}
return -1
}
The Go implementation follows the same logic as the Python version.
The range loop provides both the index and the value for each element in the slice. We compute index % 10 and compare it with the current value.
Go slices already handle dynamic lengths safely, and there are no overflow concerns because the constraints are very small. No additional memory allocation is required.
Worked Examples
Example 1
Input: nums = [0,1,2]
We scan the array from left to right.
| Index | nums[i] | i % 10 | Match? |
|---|---|---|---|
| 0 | 0 | 0 | Yes |
At index 0, the condition is satisfied immediately.
Returned value:
0
Example 2
Input: nums = [4,3,2,1]
| Index | nums[i] | i % 10 | Match? |
|---|---|---|---|
| 0 | 4 | 0 | No |
| 1 | 3 | 1 | No |
| 2 | 2 | 2 | Yes |
At index 2, the condition becomes true.
Returned value:
2
Example 3
Input: nums = [1,2,3,4,5,6,7,8,9,0]
| Index | nums[i] | i % 10 | Match? |
|---|---|---|---|
| 0 | 1 | 0 | No |
| 1 | 2 | 1 | No |
| 2 | 3 | 2 | No |
| 3 | 4 | 3 | No |
| 4 | 5 | 4 | No |
| 5 | 6 | 5 | No |
| 6 | 7 | 6 | No |
| 7 | 8 | 7 | No |
| 8 | 9 | 8 | No |
| 9 | 0 | 9 | No |
No valid index exists.
Returned value:
-1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | We scan the array once |
| Space | O(1) | Only a few variables are used |
The algorithm performs a single pass through the array, checking each index exactly once. Since each operation inside the loop takes constant time, the total running time is linear in the size of the array.
The algorithm does not allocate any extra data structures proportional to the input size, so the space complexity remains constant.
Test Cases
from typing import List
class Solution:
def smallestEqual(self, nums: List[int]) -> int:
for index, value in enumerate(nums):
if index % 10 == value:
return index
return -1
solution = Solution()
assert solution.smallestEqual([0,1,2]) == 0 # first index matches immediately
assert solution.smallestEqual([4,3,2,1]) == 2 # middle index matches
assert solution.smallestEqual([1,2,3,4,5,6,7,8,9,0]) == -1 # no valid index
assert solution.smallestEqual([0]) == 0 # single element valid
assert solution.smallestEqual([5]) == -1 # single element invalid
assert solution.smallestEqual([9,9,9,3]) == 3 # later valid index
assert solution.smallestEqual([1,1,1,1]) == 1 # multiple possible values, first valid returned
assert solution.smallestEqual([9,8,7,6,5,4,3,2,1,0,0]) == -1 # indices above 9 still checked correctly
assert solution.smallestEqual([5,6,7,8,9,0]) == 5 # modulo wrap behavior
Test Summary
| Test | Why |
|---|---|
[0,1,2] |
Verifies immediate match at first index |
[4,3,2,1] |
Verifies match in the middle |
[1,2,3,4,5,6,7,8,9,0] |
Verifies no valid answer case |
[0] |
Smallest possible valid input |
[5] |
Smallest possible invalid input |
[9,9,9,3] |
Verifies later index match |
[1,1,1,1] |
Verifies smallest matching index is returned |
[9,8,7,6,5,4,3,2,1,0,0] |
Verifies behavior for indices larger than 9 |
[5,6,7,8,9,0] |
Verifies modulo comparison logic |
Edge Cases
One important edge case is when the very first index satisfies the condition. For example, in [0,1,2], index 0 already matches because 0 % 10 = 0. A buggy implementation that delays returning or scans incorrectly could miss the requirement to return the smallest valid index. The current implementation avoids this by returning immediately upon finding the first match.
Another important edge case is when no index satisfies the condition. In [1,2,3,4,5,6,7,8,9,0], every comparison fails. Some implementations might accidentally return the last checked index or an uninitialized value. This solution correctly returns -1 only after fully completing the scan.
A third edge case involves indices larger than 9. Because the comparison uses modulo 10, index values wrap around. For example, index 15 has 15 % 10 = 5. An incorrect implementation might compare the raw index instead of the modulo result. The current implementation explicitly computes index % 10 every time, ensuring correctness for all valid input sizes.
A final edge case is a single-element array. Arrays such as [0] and [5] test whether the implementation handles minimal input sizes correctly. Since the loop naturally handles arrays of length 1, the implementation works without requiring any special handling.