# Smallest Index With Equal Value
**Difficulty:** EASY
[External](https://leetcode.com/problems/smallest-index-with-equal-value)
Canonical: https://scaleengineer.com/dsa/problems/smallest-index-with-equal-value
**Data structures:** Array
---
## Problem
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 <= 100`
* `0 <= nums[i] <= 9`

# Approaches
## Brute-Force Search with Extra Storage
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.
**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.
**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.
### Explanation
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 `nums` from index `i = 0` to `nums.length - 1`.
*   Inside the loop, for each index `i`, check if `i % 10 == nums[i]`.
*   If the condition holds true, add the index `i` to the `validIndices` list.
*   After the loop finishes, check if the `validIndices` list 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:**

```java
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);
        }
    }
}
```
### Algorithm
*   Initialize an empty list, for example, `validIndices`, to store the indices that satisfy the condition.
*   Iterate through the input array `nums` from index `i = 0` to `nums.length - 1`.
*   Inside the loop, for each index `i`, check if `i % 10 == nums[i]`.
*   If the condition holds true, add the index `i` to the `validIndices` list.
*   After the loop finishes, check if the `validIndices` list 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.

## Optimized Single-Pass Linear Scan
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.
**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.
**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.
### Explanation
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 `nums` array using an index `i`, starting from `0` up to `nums.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 `i` immediately.
*   If the loop finishes without returning, it implies that no index satisfied the condition. In this case, return -1.

**Code Snippet:**

```java
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;
    }
}
```
### Algorithm
*   Iterate through the `nums` array using an index `i`, starting from `0` up to `nums.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 `i` immediately.
*   If the loop finishes without returning, it implies that no index satisfied the condition. In this case, return -1.

# Solutions
### Java

```java
class Solution {
public
  int smallestEqual(int[] nums) {
    for (int i = 0; i < nums.length; ++i) {
      if (i % 10 == nums[i]) {
        return i;
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
class Solution:
    def smallestEqual(self, nums: List[int]) -> int: for i, v in enumerate(nums): if i % 10 == v: return i return - 1

```