algoadvance

Leetcode 2903. Find Indices With Index and Value Difference I

Problem Statement

You are given an integer array nums. You need to return all indices i such that i is equal to nums[i]. Return the list of indices in ascending order.

Clarifying Questions

  1. Q: What should we return if there are no indices that satisfy the condition?
    • A: We should return an empty list.
  2. Q: Can the input array contain negative numbers or duplicates?
    • A: The problem doesn’t specify that the input will contain negative numbers or duplicates, but we can assume typical integer array constraints unless explicitly stated otherwise.
  3. Q: What is the size range of the input array nums?
    • A: The problem is theoretical, but typically LeetCode problems might include arrays from size 0 (empty) to 10^5 elements. We will write our solution with this size range in mind for performance considerations.

Strategy

The problem requires us to identify all indices i such that the value at nums[i] is equal to i. This problem can be solved using a straightforward linear scan of the array.

Steps:

  1. Initialize an empty list to store the result.
  2. Iterate through the array with an index from 0 to the length of the array minus one.
  3. For each index i, if nums[i] equals i, add i to the result list.
  4. Return the result list.

Code

#include <vector>
#include <iostream>

std::vector<int> findIndicesWithIndexAndValueDifference(std::vector<int>& nums) {
    std::vector<int> result;
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] == i) {
            result.push_back(i);
        }
    }
    return result;
}

int main() {
    // Test case
    std::vector<int> nums = {0, 2, 2, 3, 4};
    std::vector<int> result = findIndicesWithIndexAndValueDifference(nums);

    std::cout << "Indices: ";
    for (int index : result) {
        std::cout << index << " ";
    }
    return 0;
}

Time Complexity

The above solution is efficient and straightforward, leveraging a single pass through the array to achieve the desired result.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI