659. Split Array into Consecutive Subsequences

Given an integer array nums that is sorted in ascending order, return true if and only if you can split it into one or more subsequences such that each subsequence consists of consecutive integers and has a length of at least 3.

 

Example 1:

Input: nums = [1,2,3,3,4,5]
Output: true
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3
3, 4, 5

Example 2:

Input: nums = [1,2,3,3,4,4,5,5]
Output: true
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3, 4, 5
3, 4, 5

Example 3:

Input: nums = [1,2,3,4,4,5]
Output: false

 

Constraints:

  • 1 <= nums.length <= 104
  • -1000 <= nums[i] <= 1000
  • nums is sorted in an ascending order.

Rust Solution

struct Solution;
use std::collections::HashMap;

impl Solution {
    fn is_possible(nums: Vec<i32>) -> bool {
        let mut left: HashMap<i32, usize> = HashMap::new();
        let mut end: HashMap<i32, usize> = HashMap::new();
        for &x in &nums {
            *left.entry(x).or_default() += 1;
        }

        for &x in &nums {
            if *left.entry(x).or_default() == 0 {
                continue;
            }
            if *end.entry(x - 1).or_default() > 0 {
                *left.entry(x).or_default() -= 1;
                *end.entry(x - 1).or_default() -= 1;
                *end.entry(x).or_default() += 1;
                continue;
            }
            if *left.entry(x + 1).or_default() > 0 && *left.entry(x + 2).or_default() > 0 {
                *left.entry(x).or_default() -= 1;
                *left.entry(x + 1).or_default() -= 1;
                *left.entry(x + 2).or_default() -= 1;
                *end.entry(x + 2).or_default() += 1;
                continue;
            }
            return false;
        }
        true
    }
}

#[test]
fn test() {
    let nums = vec![1, 2, 3, 3, 4, 5];
    let res = true;
    assert_eq!(Solution::is_possible(nums), res);
    let nums = vec![1, 2, 3, 3, 4, 4, 5, 5];
    let res = true;
    assert_eq!(Solution::is_possible(nums), res);
    let nums = vec![1, 2, 3, 4, 4, 5];
    let res = false;
    assert_eq!(Solution::is_possible(nums), res);
}

Having problems with this solution? Click here to submit an issue on github.