Java no extra space solution with detailed explanation


  • 0
    T

    as all the numbers are between 1 - n, so all the number can be used as index to find another element inside input array. Basic idea is to keep swapping elements in one index until find other element value which is same as value at current index, then we can just confirm that value is a duplicated value,
    for example
    if i have array 1 1 2
    at position 0, I just do int i = a[0], int j = a[a[0]];
    if i == j, means they are duplicated. then I move to next element.
    if next element is already confirmed duplicated by query result, then we just continue.
    then we can find all the duplicated elements.

    public class Solution {
        public List<Integer> findDuplicates(int[] a) {
            Set<Integer> out = new HashSet<>();
            for(int i=0; i< a.length; i++){
                while (true){
                    int v = a[i];
                    if(v - 1 == i || out.contains(v)){
                        break;
                    }
                    int pv = a[v - 1];
                    if(v == pv){
                        out.add(v);
                        break;
                    }
                    //swap value of
                    a[v - 1] = v;
                    a[i] = pv;
                }
            }
            return out.stream().collect(Collectors.toList());
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.