Smallest Index With Equal Value - Solution & Explanation

Problem Overview: Given an integer array nums, return the smallest index i such that i % 10 == nums[i]. If no index satisfies the condition, return -1. The task is mainly about scanning the array and checking a simple modulo condition.

Approach 1: Iterative Method (O(n) time, O(1) space)

The most direct solution is a single pass through the array. For each index i, compute i % 10 and compare it with nums[i]. The first index where the values match is the answer because the traversal proceeds from left to right. As soon as the condition holds, return that index immediately.

This approach relies only on sequential iteration and constant-time arithmetic operations. No additional data structures are needed. The algorithm performs exactly one comparison per element, making the time complexity O(n) and space complexity O(1). Because the problem asks for the smallest index, scanning from the beginning naturally guarantees correctness.

This is the approach most developers use in practice. The logic is minimal, easy to implement, and efficient even for large arrays. Problems involving element checks tied to index properties often reduce to a straightforward traversal over an array.

Approach 2: Divide and Conquer (O(n) time, O(log n) space)

A divide and conquer variant splits the array into two halves and recursively checks each segment for a valid index. The algorithm first searches the left half. If a valid index exists there, return it immediately because it will always be smaller than any index in the right half. If the left half contains no valid index, search the right half.

Each recursive call processes a smaller portion of the array while maintaining the original index positions for the modulo comparison. The overall number of examined elements remains n, so the time complexity stays O(n). However, recursive calls introduce a stack depth of O(log n).

This method demonstrates the mechanics of divide and conquer, but it does not provide a performance advantage over a simple loop. The modulo comparison still needs to happen for each element, and recursion only adds overhead. Still, it can be useful when practicing recursive decomposition patterns alongside simple array traversal.

Recommended for interviews: The iterative scan is the expected answer. Interviewers typically look for the observation that you only need to check each index once and can return immediately on the first match. Mentioning the O(n) time and O(1) space complexity demonstrates solid understanding. The divide and conquer version is mostly educational rather than practical.