Watch 10 video solutions for Smallest Index With Equal Value, a easy level problem involving Array. This walkthrough by CodeJulian has 1,651 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 9Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Method | O(n) | O(1) | Best for this problem. Simple linear scan and early return when the first valid index appears. |
| Divide and Conquer | O(n) | O(log n) | Useful for practicing recursive decomposition, though it adds overhead compared to iteration. |