Smallest Index With Equal Value
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves a full scan of the array to identify all indices i that satisfy the condition i mod 10 == nums[i]. These valid indices are collected in a separate list. After the scan is complete, if the list contains any indices, the smallest one is returned. If the list is empty, it signifies that no such index exists, and -1 is returned.
Algorithm
- Initialize an empty list, for example,
validIndices, to store the indices that satisfy the condition. - Iterate through the input array
numsfrom indexi = 0tonums.length - 1. - Inside the loop, for each index
i, check ifi % 10 == nums[i]. - If the condition holds true, add the index
ito thevalidIndiceslist. - After the loop finishes, check if the
validIndiceslist is empty. - If it is empty, return -1.
- Otherwise, return the first element of
validIndices, which is guaranteed to be the smallest since we added indices in increasing order.
Walkthrough
This approach involves a full scan of the array to identify all indices i that satisfy the condition i mod 10 == nums[i]. These valid indices are collected in a separate list. After the scan is complete, if the list contains any indices, the smallest one is returned. If the list is empty, it signifies that no such index exists, and -1 is returned.
Algorithm:
- Initialize an empty list, for example,
validIndices, to store the indices that satisfy the condition. - Iterate through the input array
numsfrom indexi = 0tonums.length - 1. - Inside the loop, for each index
i, check ifi % 10 == nums[i]. - If the condition holds true, add the index
ito thevalidIndiceslist. - After the loop finishes, check if the
validIndiceslist is empty. - If it is empty, return -1.
- Otherwise, return the first element of
validIndices, which is guaranteed to be the smallest since we added indices in increasing order.
Code Snippet:
import java.util.ArrayList;import java.util.List; class Solution { public int smallestEqual(int[] nums) { List<Integer> validIndices = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { if (i % 10 == nums[i]) { validIndices.add(i); } } if (validIndices.isEmpty()) { return -1; } else { return validIndices.get(0); } }}Complexity
Time
O(N), where N is the number of elements in the `nums` array. The entire array is traversed once.
Space
O(K), where K is the number of indices satisfying the condition. In the worst-case scenario (e.g., `nums = [0, 1, 2, ...]`), K can be equal to N, leading to O(N) space complexity.
Trade-offs
Pros
The logic is straightforward and easy to follow.
It correctly identifies all possible solutions before selecting the smallest one.
Cons
Uses extra space to store valid indices, which is not optimal.
It always iterates through the entire array, even if the smallest valid index is found at the beginning.
This is the most efficient approach. We can simply iterate through the array from index 0 upwards. The first index i that satisfies the condition i mod 10 == nums[i] will inherently be the smallest such index due to the nature of the linear scan. Upon finding such an index, we can immediately return it and terminate the search. If the loop completes without finding a valid index, it means none exists, and we return -1.
Algorithm
- Iterate through the
numsarray using an indexi, starting from0up tonums.length - 1. - In each iteration, check if the condition
i % 10 == nums[i]is true. - If the condition is met, it means we have found the smallest index that satisfies it. Return
iimmediately. - If the loop finishes without returning, it implies that no index satisfied the condition. In this case, return -1.
Walkthrough
This is the most efficient approach. We can simply iterate through the array from index 0 upwards. The first index i that satisfies the condition i mod 10 == nums[i] will inherently be the smallest such index due to the nature of the linear scan. Upon finding such an index, we can immediately return it and terminate the search. If the loop completes without finding a valid index, it means none exists, and we return -1.
Algorithm:
- Iterate through the
numsarray using an indexi, starting from0up tonums.length - 1. - In each iteration, check if the condition
i % 10 == nums[i]is true. - If the condition is met, it means we have found the smallest index that satisfies it. Return
iimmediately. - If the loop finishes without returning, it implies that no index satisfied the condition. In this case, return -1.
Code Snippet:
class Solution { public int smallestEqual(int[] nums) { for (int i = 0; i < nums.length; i++) { if (i % 10 == nums[i]) { return i; // Found the smallest index, return immediately. } } // If the loop finishes, no such index was found. return -1; }}Complexity
Time
O(N), where N is the length of the `nums` array. In the worst case, the entire array is scanned. However, it can be faster on average if a valid index is found early.
Space
O(1), as it uses only a constant amount of extra space regardless of the input size.
Trade-offs
Pros
Highly efficient in both time and space.
Optimal solution for this problem.
Features early exit, which can lead to better performance on average compared to a full scan.
Cons
There are no significant disadvantages to this approach for the given problem.
Solutions
Solution
class Solution {public int smallestEqual(int[] nums) { for (int i = 0; i < nums.length; ++i) { if (i % 10 == nums[i]) { return i; } } return -1; }}class Solution {public: int smallestEqual(vector<int> &nums) { for (int i = 0; i < nums.size(); ++i) if (i % 10 == nums[i]) return i; return -1; }};class Solution: def smallestEqual(self, nums: List[int]) -> int: for i, v in enumerate(nums): if i % 10 == v: return i return - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.