Arrays & Hashing
'pass'
Given an array of integers sorted in ascending order, return "pass" if and only if you can split it into one or more subsequences such that:
- Each subsequence consists of consecutive integers.
- Each subsequence has a length of at least
Example 1:
- Input:
[1, 2, 3, 3, 4, 5] - Output:
"pass" - Explanation:
You can split the array into two consecutive subsequences:[1, 2, 3][3, 4, 5]
Example 2:
- Input:
[1, 2, 3, 4, 4, 5] - Output:
"fail" - Explanation:
You cannot split the array into valid consecutive subsequences.[1, 2, 3]is valid.- However,
[4, 4, 5]is not valid because it has only two unique numbers.
import java.util.HashMap;
import java.util.Map;
public class SplitArrayIntoConsecutiveSubsequences {
public static boolean isPossible(int[] nums) {
// Count frequency of each number
Map<Integer, Integer> freq = new HashMap<>();
// Count how many subsequences need the next number
Map<Integer, Integer> appendFreq = new HashMap<>();
// Fill frequency map
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
// Try to build subsequences
for (int num : nums) {
if (freq.get(num) == 0) {
continue; // Already used this number
}
// If there's a subsequence that ends with num-1, append num to it
if (appendFreq.getOrDefault(num - 1, 0) > 0) {
appendFreq.put(num - 1, appendFreq.get(num - 1) - 1);
appendFreq.put(num, appendFreq.getOrDefault(num, 0) + 1);
}
// Otherwise, try to create a new subsequence num, num+1, num+2
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);
appendFreq.put(num + 2, appendFreq.getOrDefault(num + 2, 0) + 1);
}
// Neither option is possible, return false
else {
return false;
}
// Use the current number
freq.put(num, freq.get(num) - 1);
}
return true;
}
public static void main(String[] args) {
// Example 1
int[] nums1 = {1, 2, 3, 3, 4, 5};
System.out.println(isPossible(nums1) ? "pass" : "fail");
// Example 2
int[] nums2 = {1, 2, 3, 4, 4, 5};
System.out.println(isPossible(nums2) ? "pass" : "fail");
}
}
pass by Mahmut Salman
