Jobs

Interviews

Discussions

Smallest Index With Equal Value

Easy

Asked by:

38 views

Topics:

Arrays

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

Try coding it in LeetCode

Smallest Index With Equal Value

Easy

Asked by:

38 views

Topics:

Arrays

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible size of the input array `nums`?
Can the array `nums` contain negative numbers, and what is the range of possible values in the array?
If there are multiple indices `i` where `i mod 10 == nums[i]`, should I return the smallest such index, or is any valid index acceptable?
If no such index `i` exists where `i mod 10 == nums[i]`, what value should I return?
Is the input array guaranteed to be non-empty?

Brute Force Solution

Approach

We are given a collection of numbers. The brute force strategy involves examining each position in the collection one by one. For each position, we check if the value at that position matches a specific condition and return the first one that fits.

Here's how the algorithm would work step-by-step:

Start by looking at the very first position in the collection.
Check if the number at that position satisfies the condition: the number matches the position itself.
If it does, we've found our answer, and we can stop looking.
If it doesn't, move to the next position in the collection.
Repeat the process of checking the number at each position until either you find a position where the number matches the position, or you reach the end of the collection.
If you reach the end of the collection without finding a match, it means there's no position that satisfies the condition.

Code Implementation

def smallest_equal_index(numbers):
    for index_value in range(len(numbers)):

        # Check if the current index equals the value at the index
        if index_value % 10 == numbers[index_value]:

            # Found an index matching the condition.
            return index_value

    # No index satisfies the condition
    return -1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n at most once. In each iteration, it performs a constant-time comparison to check if nums[i] % 10 == i. If a match is found, the algorithm immediately returns. In the worst-case scenario, the algorithm iterates through all n elements without finding a match, leading to a linear time complexity of O(n).

Space Complexity

O(1) – The provided algorithm iterates through the input collection without using any additional data structures that scale with the input size N. It only uses a constant amount of extra space, such as a variable to store the current index being checked. Therefore, the space complexity is independent of the input size and is O(1).

Optimal Solution

Approach

The fastest way to solve this is to directly check the condition for each position one at a time. Since we're looking for the *smallest* position that satisfies the requirement, we can stop as soon as we find it.

Here's how the algorithm would work step-by-step:

Start checking from the beginning.
For each position, check if the number at that position is equal to the position itself when we take the remainder after dividing the position number by 10.
If we find a position where this is true, we're done - that's our answer.
If we go through all the positions and don't find one that matches, then there is no such position, and we can indicate that.

Code Implementation

def smallest_equal(numbers: list[int]) -> int:
    # Iterate through the list to find the smallest index
    for index_position in range(len(numbers)):

        # Check if the condition is met
        if index_position % 10 == numbers[index_position]:
            # Return the index if the condition is met
            return index_position

    # If no such index exists, return -1
    return -1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n at most once. In each iteration, it performs a constant-time comparison to check if nums[i] % 10 is equal to i. The loop terminates as soon as a suitable index is found, or after examining all n elements in the worst case. Therefore, the time complexity is directly proportional to the number of elements in the input array, resulting in O(n).

Space Complexity

O(1) – The algorithm iterates through the input array, checking each element. It does not use any auxiliary data structures like arrays, lists, or hash maps. The operations are performed in place, and only a constant amount of extra memory is used to store loop counters or temporary variables. Therefore, the space complexity is constant, irrespective of the input array's size N.

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 immediately as no index can satisfy the condition.
Array with a single element	Check if the element at index 0 satisfies i mod 10 == nums[i] and return 0 if true, otherwise return -1.
Large array (close to maximum allowed size)	Ensure the solution has O(n) time complexity to avoid timeouts and constant memory usage (O(1)).
Array with all elements equal	The solution should iterate through the array and return the first index i where i mod 10 equals the common element.
Array with numbers exceeding the integer limit.	Since we're looking at 'i mod 10', this has no effect, the program should still work as expected.
Array contains negative numbers.	The problem statement states that the array contains non-negative numbers, so this case should be skipped.
No index 'i' satisfies the condition 'i mod 10 == nums[i]'	Return -1 after iterating through the entire array without finding a valid index.
Integer overflow when calculating 'i mod 10' if i is extremely large	Modulo operation handles integer overflows correctly by wrapping around, so no extra handling is needed.

Null or empty input array

How to Handle:

Return -1 immediately as no index can satisfy the condition.

Array with a single element

How to Handle:

Check if the element at index 0 satisfies i mod 10 == nums[i] and return 0 if true, otherwise return -1.

Large array (close to maximum allowed size)

How to Handle:

Ensure the solution has O(n) time complexity to avoid timeouts and constant memory usage (O(1)).

Array with all elements equal

How to Handle:

The solution should iterate through the array and return the first index i where i mod 10 equals the common element.

Array with numbers exceeding the integer limit.

How to Handle:

Since we're looking at 'i mod 10', this has no effect, the program should still work as expected.

Array contains negative numbers.

How to Handle:

The problem statement states that the array contains non-negative numbers, so this case should be skipped.

No index 'i' satisfies the condition 'i mod 10 == nums[i]'

How to Handle:

Return -1 after iterating through the entire array without finding a valid index.

Integer overflow when calculating 'i mod 10' if i is extremely large

How to Handle:

Modulo operation handles integer overflows correctly by wrapping around, so no extra handling is needed.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible size of the input array `nums`?
Can the array `nums` contain negative numbers, and what is the range of possible values in the array?
If there are multiple indices `i` where `i mod 10 == nums[i]`, should I return the smallest such index, or is any valid index acceptable?
If no such index `i` exists where `i mod 10 == nums[i]`, what value should I return?
Is the input array guaranteed to be non-empty?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the very first position in the collection.
Check if the number at that position satisfies the condition: the number matches the position itself.
If it does, we've found our answer, and we can stop looking.
If it doesn't, move to the next position in the collection.
Repeat the process of checking the number at each position until either you find a position where the number matches the position, or you reach the end of the collection.
If you reach the end of the collection without finding a match, it means there's no position that satisfies the condition.

Code Implementation

def smallest_equal_index(numbers):
    for index_value in range(len(numbers)):

        # Check if the current index equals the value at the index
        if index_value % 10 == numbers[index_value]:

            # Found an index matching the condition.
            return index_value

    # No index satisfies the condition
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start checking from the beginning.
For each position, check if the number at that position is equal to the position itself when we take the remainder after dividing the position number by 10.
If we find a position where this is true, we're done - that's our answer.
If we go through all the positions and don't find one that matches, then there is no such position, and we can indicate that.

Code Implementation

def smallest_equal(numbers: list[int]) -> int:
    # Iterate through the list to find the smallest index
    for index_position in range(len(numbers)):

        # Check if the condition is met
        if index_position % 10 == numbers[index_position]:
            # Return the index if the condition is met
            return index_position

    # If no such index exists, return -1
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 immediately as no index can satisfy the condition.
Array with a single element	Check if the element at index 0 satisfies i mod 10 == nums[i] and return 0 if true, otherwise return -1.
Large array (close to maximum allowed size)	Ensure the solution has O(n) time complexity to avoid timeouts and constant memory usage (O(1)).
Array with all elements equal	The solution should iterate through the array and return the first index i where i mod 10 equals the common element.
Array with numbers exceeding the integer limit.	Since we're looking at 'i mod 10', this has no effect, the program should still work as expected.
Array contains negative numbers.	The problem statement states that the array contains non-negative numbers, so this case should be skipped.
No index 'i' satisfies the condition 'i mod 10 == nums[i]'	Return -1 after iterating through the entire array without finding a valid index.
Integer overflow when calculating 'i mod 10' if i is extremely large	Modulo operation handles integer overflows correctly by wrapping around, so no extra handling is needed.

Null or empty input array

How to Handle:

Return -1 immediately as no index can satisfy the condition.

Array with a single element

How to Handle:

Check if the element at index 0 satisfies i mod 10 == nums[i] and return 0 if true, otherwise return -1.

Large array (close to maximum allowed size)

How to Handle:

Ensure the solution has O(n) time complexity to avoid timeouts and constant memory usage (O(1)).

Array with all elements equal

How to Handle:

The solution should iterate through the array and return the first index i where i mod 10 equals the common element.

Array with numbers exceeding the integer limit.

How to Handle:

Since we're looking at 'i mod 10', this has no effect, the program should still work as expected.

Array contains negative numbers.

How to Handle:

The problem statement states that the array contains non-negative numbers, so this case should be skipped.

No index 'i' satisfies the condition 'i mod 10 == nums[i]'

How to Handle:

Return -1 after iterating through the entire array without finding a valid index.

Integer overflow when calculating 'i mod 10' if i is extremely large

How to Handle:

Modulo operation handles integer overflows correctly by wrapping around, so no extra handling is needed.