Java, No HashSet, No duplicates, O(1) extra space solution


  • -4
    E
    public int[] intersection(int[] nums1, int[] nums2) {
        //special cases
        if (nums1 == null || nums2 == null) {
            return new int[0];
        }
        
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        //save results
        List<Integer> res = new ArrayList<Integer>();
        
        int i = 0;
        int j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                ++i;
            } else if (nums1[i] > nums2[j]) {
                ++j;
            } else {
                res.add(nums1[i]);
                ++i;
                ++j;
            }
    
            //critical invariant: i and j both are the first elements of a duplicate region
            while (i >=1 && i < nums1.length && nums1[i] == nums1[i-1]) {
                ++i;
            }
            
             while (j >=1 && j < nums2.length && nums2[j] == nums2[j-1]) {
                ++j;
            }
        }
        
        //convert res list to an array
        int[] output = new int[res.size()];
        int k = 0;
        for (int x : res) {
            output[k++] = x;
        }
        
        return output;
    }

  • 0
    E

    My version does not use hashset to remove duplicates. Rather it uses only two pointers to produce the result.
    I don't understand the folks who hands down on the solution. It is normal that during the interview, you are asked to implement it without using any hashing.


  • 0
    N

    ? int[] C = new int[Math.min(nums1.length, nums2.length)];

    looks like O(n) space to me


  • 0
    E

    an intermediary collection is necessary. because it asks to return a int[], rather than a list.


  • 0
    V

    Problem with your code is the sorting (NlogN) which you are doing with each arrays. It is the reason for down votes. Also it depends on the interviewer which approach he wants you to follow if he is interested in time complexity then he wants to see HashSet.


  • 0
    E

    of course it is trivial to use hashset to get O(n).
    my solution is intended for a following up question: can you do it without hashing?


Log in to reply
 

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