# 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.

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

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

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