Sort, then expand each subsequence as much as possible, the tail with thank you.
Approach
we can use bucket sort or a bitset
Complexity
Time complexity: O(nlogn)
Space complexity: O(n)
Code
// 61ms
fun partitionArray(n: IntArray, k: Int): Int {
n.sort(); var l = -k - 1
return n.count { r -> (r - l > k).also { if (it) l = r } }
}
// 9ms
fun partitionArray(n: IntArray, k: Int): Int {
val f = java.util.BitSet(100001); for (x in n) f.set(x)
var cnt = 0; var l = -k-1; var r = f.nextSetBit(0)
while (r >= 0) {
if (r - l > k) { l = r; ++cnt }
r = f.nextSetBit(r + 1)
}
return cnt
}
// 8ms
fun partitionArray(n: IntArray, k: Int): Int {
val f = IntArray(100001); for (x in n) f[x] = x + 1
var cnt = 0; var l = -k
for (r in f) if (r - l > k) { l = r; ++cnt }
return cnt
}
// 1ms
pub fn partition_array(n: Vec<i32>, k: i32) -> i32 {
let (mut f, mut l) = ([0; 100001], -k);
for x in n { f[x as usize] = x + 1 }
f.iter().filter(|&&r| { let w = r - l > k; if w { l = r }; w }).count() as _
}
// 4ms
int partitionArray(vector<int>& n, int k) {
bitset<100001>f; int l = -k-1, c = 0;
for (int x: n) f[x] = 1;
for (int r = 0; r < 100001; ++r) if (f[r] && r - l > k) ++c, l = r;
return c;
}
