LeetCode Entry

594. Longest Harmonious Subsequence

30.06.2025 easy 2025 kotlin rust

Longest subsequence with max-min=1 pointers

594. Longest Harmonious Subsequence easy blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1035

Problem TLDR

Longest subsequence with max-min=1 #easy #counting #sort #two_pointers

Intuition

Calculate the frequencies. For each value x find count x-1 and x+1.

Another was: sort, then linear scan.

Approach

  • should be exactly 1, not at most
  • we can check only the x + 1 (because we x - 1 would still be checked)

Complexity

  • Time complexity: \(O(n\)

  • Space complexity: \(O(n)\)

Code


// 25ms
    fun findLHS(n: IntArray): Int {
        val f = n.groupBy { it }
        return f.maxOf { (k, v) -> v.size + (f[k + 1]?.size ?: -v.size) }
    }



// 0ms
    pub fn find_lhs(mut n: Vec<i32>) -> i32 {
        n.sort_unstable(); n.chunk_by(|a, b| b - a < 1)
        .collect::<Vec<_>>().windows(2)
        .map(|w| if w[1][0] - w[0][0] == 1 { w[0].len() + w[1].len() } else { 0 })
        .max().unwrap_or(0) as _
    }



// 6ms
    int findLHS(vector<int>& n) {
        sort(begin(n), end(n)); int r = 0;
        for (int i = 1, j = 0; i < size(n); ++i) {
            while (j < i && n[i] - n[j] > 1) j++;
            if (n[i] - n[j] == 1) r = max(r, i - j + 1);
        } return r;
    }