O(n) time O(n) space solution to return n-th max


  • 0
    V
        public int thirdMax(int[] nums) {
            nums = removeDuplicates(nums);
             // by changing order value we can get any n-th max
            int order = 3;
            if(nums.length < order) order = 1; 
            int f = 0;
            int e = nums.length;
            while(true) {
                int partPoint = partition(nums, f, e);
                if(partPoint  == order - 1) return nums[partPoint];
                if(partPoint > order - 1) {
                    e = partPoint;
                } else {
                    f = partPoint;
                }
            }
        }
        
        private int[] removeDuplicates(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for(int n: nums) {
                set.add(n);
            }
            int[] res = new int[set.size()];
            int i = 0;
            for(int n : set) {
                res[i++] = n;
            }
            return res;
        }
        
        private int partition(int[] nums, int f, int e) {
            if (e - f == 1) return f;
            int pivot = nums[e - 1];
            int j = f - 1; 
            for(int i = f; i < e - 1; i++) {
                  if(nums[i] >= pivot) {
                      j += 1;
                      swap(nums, i, j);
                  }
            }
            j += 1;
            swap(nums, e - 1, j);
            return j;
        }
        
        
        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    
    

  • 0
    J

    In a real interview, they will ask you what if instead of having an array, we now have a number stream?


  • 0
    V

    They might ask that. But if with this O(n) space solution there is no difference at all as you have a copy of the incoming data.


Log in to reply
 

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