Split array into consecutive subsequences

Array Hash Table Greedy Heap (Priority Queue)

52.0% acceptance

Feb 20, 2026

4567

814

Given an array nums of integers, return whether it is possible to split it into one or more subsequences such that each subsequence consists of consecutive integers and has length at least 3.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;
impl Solution {
  pub fn is_possible(nums: Vec<i32>) -> bool {
    let mut freq: HashMap<i32, i32> = HashMap::new();
    let mut tail: HashMap<i32, i32> = HashMap::new();
    for &n in &nums {
      *freq.entry(n).or_insert(0) += 1;
    }
    for &n in &nums {
      if *freq.get(&n).unwrap_or(&0) == 0 {
        continue;
      }
      if *tail.get(&n).unwrap_or(&0) > 0 {
        *tail.entry(n).or_insert(0) -= 1;
        *tail.entry(n + 1).or_insert(0) += 1;
        *freq.entry(n).or_insert(0) -= 1;
      } else if *freq.get(&(n + 1)).unwrap_or(&0) > 0
        && *freq.get(&(n + 2)).unwrap_or(&0) > 0
      {
        *freq.entry(n).or_insert(0) -= 1;
        *freq.entry(n + 1).or_insert(0) -= 1;
        *freq.entry(n + 2).or_insert(0) -= 1;
        *tail.entry(n + 3).or_insert(0) += 1;
      } else {
        return false;
      }
    }
    true
  }
}