Java O(nlgn) solution 42ms beats 99.71% @ 2017-07-02 00:28:19


  • 0

    Sort first, then do a one pass to find the longest length desired. Does not employ hashtables. Only keep two pointers to speed up the algorithm.

    public class Solution {
        public int findLHS(int[] nums) {
            Arrays.sort(nums);
            int maxLen = 0;
            int firstPrev = 0, secondPrev = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > nums[firstPrev]) {
                    if (nums[i] - nums[firstPrev] == 1) {
                        if (nums[i] > nums[secondPrev]) secondPrev = i;
                    } else if (nums[i - 1] - nums[firstPrev] == 1) {
                        maxLen = Math.max(maxLen, i - firstPrev);
                        if (nums[i] - nums[i - 1] == 1) {
                            firstPrev = secondPrev;
                            secondPrev = i;
                        } else {
                            firstPrev = secondPrev = i;
                        }
                    } else firstPrev = secondPrev = i;
                }
            }
            return Math.max(maxLen, secondPrev > firstPrev ? (nums.length - firstPrev) : 0);
        }
    }
    

    We track the closest run of k and k + 1 with firstPrev and secondPrev

    • firstPrev: index of the leftmost k
    • secondPrev: index of the leftmost k + 1.

    The logic can be a little intricate. The cases below should help understand the algorithm. Especially, the last branch of the conditional logic deals specifically a situation that arises in input6.

            int[] input1 = {1,3,2,2,5,2,3,7};//5
            int[] input2 = {1,3,5,7,9,11,13,15,17};//0
            int[] input3 = {4289383,46930886,81692777,14636915,57747793,24238335,19885386,49760492,96516649,89641421};//0
            int[] input4 = {1,3,2,2,5,2,3,6,2,1,2,3,2,3,2,3,2,3,7};//5
            int[] input5 = {1,2,2,1};//4
            int[] input6 = {1,2,3,3,1,-14,13,4};//3
    

    My original idea was to use hashing, which also saves the trouble of sorting at all. But input3 broke that approach.

    I submitted the code twice, with time 43ms(99.61%) and 42ms(99.71%).

    Despite the benchmarking purpose, I do think the more important version of solution is the O(n) hashtable solution. Overheads cause leetcode OJ to sorta penalize using hashtables, but in real interviews, I think hashtable is the better choice to go with.


Log in to reply
 

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