659. Split Array into Consecutive Subsequences

leetcode medium

#array#csharp#hash-table#leetcode#medium#sort

Task

Вам дан отсортированный в неубывающем порядке массив целых чисел nums.

Определите, можно ли разделить nums на одну или несколько подпоследовательностей так, чтобы выполнялись оба следующих условия:

Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).

Все подпоследовательности имеют длину 3 или более.

Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.

Подпоследовательность массива — это новый массив, который формируется из исходного массива путем удаления некоторых (может быть, ни одного) элементов без нарушения относительных позиций оставшихся элементов. (например, [1,3,5] является подпоследовательностью [1,2,3,4,5], тогда как [1,3,2] не является).

Пример

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

Output: true

C# solution

matched/original

using System.Collections.Generic;
public class Solution {
    public bool IsPossible(int[] nums) {
        var freq = new Dictionary<int, int>();
        var need = new Dictionary<int, int>();
        
        foreach (var num in nums) {
            if (freq.ContainsKey(num)) {
                freq[num]++;
            } else {
                freq[num] = 1;
            }
        }
        
        foreach (var num in nums) {
            if (freq[num] == 0) continue;
            if (need.ContainsKey(num) && need[num] > 0) {
                need[num]--;
                if (need.ContainsKey(num + 1)) {
                    need[num + 1]++;
                } else {
                    need[num + 1] = 1;
                }
            } else if (freq.ContainsKey(num + 1) && freq[num + 1] > 0 &&
                       freq.ContainsKey(num + 2) && freq[num + 2] > 0) {
                freq[num + 1]--;
                freq[num + 2]--;
                if (need.ContainsKey(num + 3)) {
                    need[num + 3]++;
                } else {
                    need[num + 3] = 1;
                }
            } else {
                return false;
            }
            freq[num]--;
        }
        
        return true;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsPossible(vector<int>& nums) {
        var freq = new unordered_map<int, int>();
        var need = new unordered_map<int, int>();
        
        foreach (var num in nums) {
            if (freq.count(num)) {
                freq[num]++;
            } else {
                freq[num] = 1;
            }
        }
        
        foreach (var num in nums) {
            if (freq[num] == 0) continue;
            if (need.count(num) && need[num] > 0) {
                need[num]--;
                if (need.count(num + 1)) {
                    need[num + 1]++;
                } else {
                    need[num + 1] = 1;
                }
            } else if (freq.count(num + 1) && freq[num + 1] > 0 &&
                       freq.count(num + 2) && freq[num + 2] > 0) {
                freq[num + 1]--;
                freq[num + 2]--;
                if (need.count(num + 3)) {
                    need[num + 3]++;
                } else {
                    need[num + 3] = 1;
                }
            } else {
                return false;
            }
            freq[num]--;
        }
        
        return true;
    }
}

Java solution

matched/original

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        Map<Integer, Integer> need = new HashMap<>();
        
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        for (int num : nums) {
            if (freq.get(num) == 0) continue;
            if (need.getOrDefault(num, 0) > 0) {
                need.put(num, need.get(num) - 1);
                need.put(num + 1, need.getOrDefault(num + 1, 0) + 1);
            } else if (freq.getOrDefault(num + 1, 0) > 0 && freq.getOrDefault(num + 2, 0) > 0) {
                freq.put(num + 1, freq.get(num + 1) - 1);
                freq.put(num + 2, freq.get(num + 2) - 1);
                need.put(num + 3, need.getOrDefault(num + 3, 0) + 1);
            } else {
                return false;
            }
            freq.put(num, freq.get(num) - 1);
        }
        
        return true;
    }
}

JavaScript solution

matched/original

var isPossible = function(nums) {
    let freq = new Map();
    let need = new Map();

    for (let num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }

    for (let num of nums) {
        if (freq.get(num) === 0) {
            continue;
        }

        if (need.get(num) > 0) {
            need.set(num, need.get(num) - 1);
            need.set(num + 1, (need.get(num + 1) || 0) + 1);
        } else if (freq.get(num + 1) > 0 && freq.get(num + 2) > 0) {
            freq.set(num + 1, freq.get(num + 1) - 1);
            freq.set(num + 2, freq.get(num + 2) - 1);
            need.set(num + 3, (need.get(num + 3) || 0) + 1);
        } else {
            return false;
        }
        freq.set(num, freq.get(num) - 1);
    }

    return true;
};

Go solution

matched/original

func isPossible(nums []int) bool {
    freq := make(map[int]int)
    need := make(map[int]int)
    
    for _, num := range nums {
        freq[num]++
    }
    
    for _, num := range nums {
        if freq[num] == 0 {
            continue
        }
        if need[num] > 0 {
            need[num]--
            need[num+1]++
        } else if freq[num+1] > 0 && freq[num+2] > 0 {
            freq[num+1]--
            freq[num+2]--
            need[num+3]++
        } else {
            return false
        }
        freq[num]--
    }
    
    return true
}

Explanation

Algorithm

Подсчет частоты элементов:

Создайте хеш-таблицу для подсчета количества вхождений каждого элемента в массиве nums.

Создание подпоследовательностей:

Создайте хеш-таблицу для отслеживания количества подпоследовательностей, которые могут быть продолжены для каждого элемента.

Пройдите по каждому элементу в массиве и выполните следующие действия:

Если элемент можно добавить к существующей подпоследовательности (проверяя хеш-таблицу подпоследовательностей), добавьте его и обновите хеш-таблицу.

Если элемент нельзя добавить к существующей подпоследовательности, начните новую последовательность длиной 3 или более элементов.

Если ни одно из условий не выполнено, верните false.

Проверка результата:

Верните true, если все элементы успешно распределены по подпоследовательностям.

😎