Is there an O(n) way to find all indices of a value in an array? [closed]

Requirement

• find all indices in new int[]{2, 1, 3, 1, 4, 2, 1, 3}
• The time complexity is within O(n)

Example

• The index of 1 are 1, 3, 6
• The index of 2 are 0, 5
• The index of 3 are 2, 7
• The index of 4 are 4

Answer

Yes, it is possible.

1. Iterate your array and use a key-value paired Data structure to store one item as a key and its indexes as value.

2. Eventually at the end you would get all items and their corresponding indexes.

3. now you can either return the key-value paired DS or you can explore it as your requirements.

Basically, you are iterating the array n-number of times where n-is the total elements present in the array. So overall complexity is: O(n)

   int [] arr = new int[]{2, 1, 3, 1, 4, 2, 1, 3};
   

    Map<Integer, List<>> hashMap = new HashMap<>();
       for(int i=0; i<arr.length; i++){
          if(hashMap.contains(arr[i])){
               hashMap.put(arr[i], hashMap.get(arr[i]).add(i);
          }else{
               hash.put(arr[i], new ArrayList<>());
          }
       }
    
       // at the end you would have a map that contains indexes of every item