Problem Description

You are given a 0-indexed integer array nums. Your task is to find the smallest index i in the array that satisfies the condition: i mod 10 == nums[i].

The modulo operation x mod y gives the remainder when x is divided by y. For example:

• 0 mod 10 = 0
• 7 mod 10 = 7
• 15 mod 10 = 5
• 23 mod 10 = 3

You need to check each index position and see if the remainder when that index is divided by 10 equals the value at that position in the array. If multiple indices satisfy this condition, return the smallest one. If no index satisfies the condition, return -1.

For example, if nums = [0, 1, 2]:

• At index 0: 0 mod 10 = 0, and nums[0] = 0. The condition is satisfied.
• At index 1: 1 mod 10 = 1, and nums[1] = 1. The condition is satisfied.
• At index 2: 2 mod 10 = 2, and nums[2] = 2. The condition is satisfied.

Since we want the smallest index, we would return 0.

Intuition

The problem asks for the smallest index that satisfies a specific condition, which immediately suggests a linear search from left to right. Since we want the smallest index, we should check indices in ascending order starting from 0.

The key insight is that we don't need any complex data structures or algorithms here. We simply need to:

1. Check each index one by one
2. Test if the condition i mod 10 == nums[i] holds
3. Return immediately when we find the first match

Why does this work? Because iterating from index 0 onwards guarantees that the first index we find satisfying the condition is automatically the smallest one. There's no need to check all indices and then compare - we can return as soon as we find a match.

The modulo 10 operation is straightforward: it gives us the last digit of the index. For indices 0 through 9, i mod 10 simply equals i. For index 10, it wraps back to 0, for 11 it becomes 1, and so on. This creates a repeating pattern every 10 indices.

Since the problem guarantees we're looking for exact equality between i mod 10 and nums[i], and both are integers, we can use a simple equality check. If we traverse the entire array without finding any matching index, we return -1 as specified.

Solution Approach

The solution uses a simple traversal approach to find the smallest index that satisfies the condition.

We iterate through the array using Python's enumerate() function, which gives us both the index i and the value x at that index simultaneously. This is more elegant than using a traditional for loop with range.

For each index-value pair (i, x):

1. We calculate i % 10 to get the remainder when the index is divided by 10
2. We check if this remainder equals the value x (which is nums[i])
3. If the condition i % 10 == x is satisfied, we immediately return i

The implementation looks like this:

for i, x in enumerate(nums):
    if i % 10 == x:
        return i

Since we traverse from left to right (starting at index 0), the first index that satisfies the condition is guaranteed to be the smallest one. This eliminates the need to track the minimum index or continue searching after finding a match.

If the loop completes without finding any index that satisfies the condition, we return -1 to indicate that no such index exists:

return -1

The time complexity is O(n) where n is the length of the array, as we potentially need to check every element. The space complexity is O(1) since we only use a constant amount of extra space regardless of the input size.

Example Walkthrough

Let's walk through the solution with the example nums = [4, 3, 2, 7, 8, 2, 3, 1].

We'll iterate through each index from left to right and check if i mod 10 == nums[i]:

Index 0:

• Calculate: 0 % 10 = 0
• Check: Does 0 == nums[0]? Does 0 == 4? No
• Continue to next index

Index 1:

• Calculate: 1 % 10 = 1
• Check: Does 1 == nums[1]? Does 1 == 3? No
• Continue to next index

Index 2:

• Calculate: 2 % 10 = 2
• Check: Does 2 == nums[2]? Does 2 == 2? Yes!
• Since we found a match, immediately return 2

We don't need to check the remaining indices (3 through 7) because we're looking for the smallest index that satisfies the condition, and we found it at index 2.

Let's verify with another example where no match exists: nums = [1, 2, 3, 4, 5]

• Index 0: 0 % 10 = 0, but nums[0] = 1. No match.
• Index 1: 1 % 10 = 1, but nums[1] = 2. No match.
• Index 2: 2 % 10 = 2, but nums[2] = 3. No match.
• Index 3: 3 % 10 = 3, but nums[3] = 4. No match.
• Index 4: 4 % 10 = 4, but nums[4] = 5. No match.

Since we've checked all indices without finding a match, we return -1.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the algorithm uses a single for loop that iterates through each element of the array exactly once in the worst case (when no element satisfies the condition i % 10 == x or the satisfying element is at the end of the array).

The space complexity is O(1). The algorithm only uses a constant amount of extra space regardless of the input size. The variables i and x used in the enumeration are the only additional space required, and they don't scale with the size of the input array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Modulo Constraint

Pitfall: A common mistake is assuming that any value in the array could satisfy the condition, when in reality, only values from 0 to 9 can ever match i % 10.

Since i % 10 always produces a remainder between 0 and 9, if nums[i] contains a value outside this range (negative numbers or values ≥ 10), that index can never satisfy the condition.

Example of the issue:

nums = [10, 11, 12]
# Index 0: 0 % 10 = 0, but nums[0] = 10 (will never match)
# Index 1: 1 % 10 = 1, but nums[1] = 11 (will never match)

Solution: While the original code handles this correctly by simply checking the condition, you could optimize by adding an early skip:

class Solution:
    def smallestEqual(self, nums: List[int]) -> int:
        for index, value in enumerate(nums):
            # Skip values that can never satisfy the condition
            if value < 0 or value > 9:
                continue
          
            if index % 10 == value:
                return index
      
        return -1

2. Off-by-One Error with 1-Indexed Thinking

Pitfall: Some developers might mistakenly think in 1-indexed terms (common in mathematics or some other programming languages), leading to incorrect modulo calculations.

Example of incorrect thinking:

# WRONG: Treating the first element as index 1
for i in range(len(nums)):
    if (i + 1) % 10 == nums[i]:  # This is incorrect!
        return i

Solution: Remember that the problem explicitly states the array is 0-indexed. The first element is at index 0, not 1. The correct approach is:

for i in range(len(nums)):
    if i % 10 == nums[i]:  # Correct: using i directly
        return i

3. Attempting to Find All Matches First

Pitfall: Some might try to collect all matching indices first and then return the minimum, which is inefficient:

# Inefficient approach
matching_indices = []
for i, x in enumerate(nums):
    if i % 10 == x:
        matching_indices.append(i)

return min(matching_indices) if matching_indices else -1

Solution: Since we traverse from left to right starting at index 0, the first match we find is guaranteed to be the smallest. Return immediately upon finding the first match:

for i, x in enumerate(nums):
    if i % 10 == x:
        return i  # Return immediately - this is the smallest
return -1

This approach is more efficient in both time (early termination) and space (no extra list needed).