Single pass using HashMap, no sorting


  • 0
    D

    I use a map to store 3 values about each element n: [top, bottom, flat].
    top is the count of n+1.
    bottom is the count of n-1.
    flat is the count of n.
    If n isn't encountered before, default to [0,0,1], else increment flat. After that check if we've encountered n+1 and/or n-1.
    If encountered n+1 before, then increment top for n by (flat count of n + 1) - (top count of n). Also increment bottom for n+1.
    If encountered n-1 before, then increment bottom for n by (flat count of n - 1) - (bottom count of n). Also increment top for n-1.
    Finally, if either top > 0 or bottom > 0 for n, then max is the maximum between max, top+flat and bottom+flat.
    Apologies if my explanation is confusing. Code provided below.

    Javascript version:

    var findLHS = function(nums) {
        if (nums.length < 2) {
            return 0;
        }
        var map = {};
        var max = 0;
        map[nums[0]] = [0, 0, 1]; // [top, bottom, flat]
        var curr;
        for (var i = 1; i < nums.length; i++) {
            var n = nums[i];
            if (!map.hasOwnProperty(n)) {
                map[n] = [0, 0, 1];
            } else {
                map[n][2]++;
            }
            curr = map[n];
            if (map.hasOwnProperty(n + 1)) {
                curr[0] += map[n+1][2] - curr[0];
                map[n + 1][1]++;
            }
            if (map.hasOwnProperty(n - 1)) {
                curr[1] += map[n-1][2] - curr[1];
                map[n - 1][0]++;
            }
            if (curr[0] > 0 || curr[1] > 0) {
                max = Math.max(max, curr[0] + curr[2], curr[1] + curr[2]);
            }
        }
        return max;
    };
    

    Java version:

    public int findLHS(int[] nums) {
            if (nums.length < 2) {
                return 0;
            }
            Map<Integer, int[]> map = new HashMap<>();
            int max = 0;
            map.put(nums[0], new int[]{0, 0, 1}); // [top, bottom, flat]
            for (int i = 1; i < nums.length; i++) {
                int n = nums[i];
                if (map.containsKey(n)) {
                    map.get(n)[2]++;
                } else {
                    map.put(n, new int[]{0, 0, 1});
                }
                int[] curr = map.get(n);
                int[] top = map.get(n+1);
                int[] bottom = map.get(n-1);
                if (top != null) {
                    curr[0] += top[2] - curr[0];
                    top[1]++;
                }
                if (bottom != null) {
                    curr[1] += bottom[2] - curr[1];
                    bottom[0]++;
                }
                if (curr[0] > 0 || curr[1] > 0) {
                    max = Math.max(max, Math.max(curr[0] + curr[2], curr[1] + curr[2]));
                }
            }
            return max;
        }
    }
    

Log in to reply
 

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