2057. Smallest Index With Equal Value

Problem Description

The problem provides an array nums, which has non-negative integers, and it is indexed from 0, meaning it's a 0-indexed array. The task is to find the index i in this array which satisfies the condition i mod 10 == nums[i]. Here, i mod 10 means the remainder when the index i is divided by 10. If such an index exists, the function should return the smallest one; if no such index exists, the function should return -1.

Simply put, you need to check each element in the list and see if the index of that element has the same remainder when divided by 10 as the value of the element itself. The question asks for the smallest index where this condition is true, meaning if the condition is true for multiple indices, you should return the first one (smallest index) you find that satisfies the condition.

Intuition

To solve this problem, we can take a straightforward approach by iterating over each element in the array and checking the condition for each index.

We start from the first element (at index 0), then proceed to the second element (index 1), and so on.
At each step, we perform the modulo operation (i % 10) and check if it equals the value of the element at that index (nums[i]). The modulo operation finds the remainder when i is divided by 10.
The moment we find a match, we know we have found the smallest index that satisfies the condition, because we are moving from the start of the array towards the end. Hence, we can immediately return the current index.
If we go through the entire array without finding any index that satisfies the condition, we return -1, as directed by the problem statement.

The algorithm has a linear time complexity O(n) because, in the worst case, we might have to check every element until we find the correct index or determine that no such index exists.

Solution Approach

The solution uses a simple for loop to iterate over the array. This approach does not require any additional data structures or complex algorithms. The pattern used is direct iteration, which is often the go-to strategy for problems that require examining each element of a collection one by one.

Here are the steps followed in the solution:

Utilize Python's built-in enumerate() function to get both the index i and the value v at that index while iterating through nums. This is a common Python pattern for when you need to access both the elements and their indices in a list.
Use the modulo operator % to calculate i % 10 at each step. In Python, x % y returns the remainder of x divided by y.
Compare the result of i % 10 with the current value v. If they are equal, immediately return the current index i because that's the smallest index that satisfies the condition. This step is the implementation of the condition provided in the problem description.
If the loop terminates without finding any index meeting the condition, return -1. This is achieved using a single return statement at the end of the function, ensuring that the function exits with the correct value if no valid index is found during the iteration.

The overall structure of the solution is straightforward, with simplicity being a key virtue here. There is no optimization or shortcut because the problem requires checking each index explicitly and the problem description does not provide any constraints that would allow for skipping certain elements.

By following these steps, the function implemented in Python meets the problem's requirements with an efficient and easily understandable solution.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small array nums to demonstrate the solution approach:

nums = [0, 2, 9, 4, 7, 1]

We will walk through the list and apply the steps provided in the solution approach:

Start with the first element:
- Index i = 0, Value v = nums[i] = 0
- Calculate i % 10 = 0 % 10 = 0
- Compare i % 10 with nums[i]. Since both are 0, the condition is satisfied.
- Return the index 0 as it satisfies i % 10 == nums[i].

The function would thus conclude at the very first step since the first index (which is the smallest possible index) contains a value equal to i % 10. There is no need to continue checking the following elements, as we were tasked with finding the smallest index that satisfies the condition. The function would return 0 in this case.

However, for the sake of illustration, let's assume we continue to check other elements (although, in practice, the function would have stopped at the first matching index):

Look at the second element (although this step would be skipped in an actual implementation once a match is found):
- Index i = 1, Value v = nums[i] = 2
- Calculate i % 10 = 1 % 10 = 1
- Compare i % 10 with nums[i]. Since 1 != 2, the condition is not satisfied.
Look at the third element:
- Index i = 2, Value v = nums[i] = 9
- Calculate i % 10 = 2 % 10 = 2
- Compare i % 10 with nums[i]. Since 2 != 9, the condition is not satisfied.
Continue this process for the remaining elements:
- For i = 3, nums[i] = 4, i % 10 = 3. But 3 != 4, condition not satisfied.
- For i = 4, nums[i] = 7, i % 10 = 4. But 4 != 7, condition not satisfied.
- For i = 5, nums[i] = 1, i % 10 = 5. But 5 != 1, condition not satisfied.

Since we found a match at the very first index (index 0), the function would have returned 0. If the first element did not satisfy i % 10 == nums[i], the function would continue checking subsequent indices in the same way until either a matching index is found or the end of the array is reached, in which case the function would return -1.

Solution Implementation

1class Solution:
2    def smallestEqual(self, nums: List[int]) -> int:
3        # Iterate over the list of numbers with their indices.
4        for index, value in enumerate(nums):
5            # Check if the current index modulo 10 equals the value.
6            if index % 10 == value:
7                # If condition matches, return the current index.
8                return index
9        # If no index-value match found, return -1.
10        return -1
11

1class Solution {
2    public int smallestEqual(int[] nums) {
3        // Loop over each element in the given array
4        for (int index = 0; index < nums.length; ++index) {
5            // Check if the current index mod 10 equals the value at this index in the array
6            if (index % 10 == nums[index]) {
7                // If condition is true, return the current index as the answer
8                return index;
9            }
10        }
11        // If no index satisfies the condition, return -1
12        return -1;
13    }
14}
15

1#include <vector>
2
3/**
4 * Finds the smallest index such that the index divided by 10 gives the same remainder as the value at that index.
5 * @param nums A vector of integers to be searched.
6 * @return The smallest index fulfilling the condition or -1 if no such index exists.
7 */
8int smallestEqual(std::vector<int>& nums) {
9    // Iterate through the vector of numbers
10    for (int index = 0; index < nums.size(); ++index) {
11        // Check if the current index modulo 10 is equal to the value at that index
12        if (index % 10 == nums[index]) {
13            // If the condition is satisfied, return the current index
14            return index;
15        }
16    }
17    // If no index satisfies the condition, return -1
18    return -1;
19}
20

1/**
2 * Finds the smallest index such that the index divided by 10 gives the same remainder as the value at that index.
3 * @param {number[]} nums - An array of numbers to be searched.
4 * @returns {number} The smallest index fulfilling the condition or -1 if no such index exists.
5 */
6function smallestEqual(nums: number[]): number {
7    // Iterate through the array of numbers
8    for (let index = 0; index < nums.length; index++) {
9        // Check if the current index modulo 10 is equal to the value at that index
10        if (index % 10 === nums[index]) {
11            // If condition is satisfied, return the current index
12            return index;
13        }
14    }
15    // If no index satisfies the condition, return -1
16    return -1;
17}
18

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the nums list. This is because the function involves a single loop that iterates through each element of the list exactly once.

The space complexity of the code is O(1), which means it uses a constant amount of extra space. The space used does not depend on the input size, as it only utilizes a few variables for its operations, regardless of the length of the input list.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know