Smallest Index With Equal Value - Solution & Explanation
Problem Statement
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
Approach Overview
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.
Approach 1: Approach 1: Iterative Method
This approach involves using a simple iterative method to solve the problem. The idea is to loop through the data structure, process elements, and maintain a result based on conditions.
The function solve iteratively adds each element of the array arr and produces the sum as a result.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Approach 2: Divide and Conquer
This approach uses the divide and conquer strategy, which involves dividing the problem into sub-problems, solving each sub-problem independently, and combining the results.
This C function sum recursively divides the array into halves, sums each half, and returns the total sum.
Complexity
Time Complexity: O(n log n)
Space Complexity: O(log n), due to recursion stack space.
Approach 3: Traversal
We directly traverse the array. For each index i, we check if it satisfies i bmod 10 = nums[i]. If it does, we return the current index i.
If we traverse the entire array and do not find a satisfying index, we return -1.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Method | Time Complexity: O(n) |
| Approach 2: Divide and Conquer | Time Complexity: O(n log n) |
| Traversal | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Leetcode | 2057. Smallest Index With Equal Value | Easy | Java Solution • Developer Docs • 1,080 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Smallest Index With Equal Value easy or hard?
Smallest Index With Equal Value Python/Java solution
How to solve Smallest Index With Equal Value in O(n)?
What is the best approach for Smallest Index With Equal Value?
Is Smallest Index With Equal Value asked at Google/Amazon/Meta?
What data structure is used in Smallest Index With Equal Value?
What is the time complexity of Smallest Index With Equal Value?
Ready to solve this problem?
Practice Smallest Index With Equal Value with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor