LeetCode Entry
1652. Defuse the Bomb
Next +-k window sums window
1652. Defuse the Bomb easy
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/804
Problem TLDR
Next +-k window sums #easy #sliding_window
Intuition
The problem size is small, do a brute force.
Approach
- to prevent off-by-ones use explicit branches of
k > 0,k < 0
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun decrypt(c: IntArray, k: Int) = IntArray(c.size) {
(min(it, it + k)..max(it, it + k))
.sumBy { c[(it + c.size) % c.size] } - c[it]
}
pub fn decrypt(c: Vec<i32>, k: i32) -> Vec<i32> {
(0..c.len() as i32).map(|i|
(i.min(i + k)..=i.max(i + k))
.map(|j| c[(j as usize + c.len()) % c.len()])
.sum::<i32>() - c[i as usize]).collect()
}
vector<int> decrypt(vector<int>& c, int k) {
int sgn = k > 0 ? 1 : -1, s = 0, n = c.size(), d;
vector<int> r(n, 0); if (k == 0) return r;
if (k < 0) for (int i = n + k; i < n; ++i) s += c[i];
if (k > 0) for (int i = 0; i < k; ++i) s += c[i];
for (int i = 0; i < n; ++i) d = c[i] - c[(i + n + k) % n],
s -= sgn * d, r[i] = k > 0 ? s : s - d;
return r;
}