1652. Defuse the Bomb

📝 Problem Details

• Title: 1652. Defuse the Bomb
• Link: https://leetcode.com/problems/defuse-the-bomb/
• Difficulty: Easy
• Tags/Categories: Sliding-Window

💭What Were My Initial Thoughts?

- fixed sliding window 
- the sliding window needs to be maintained in the circular array

🤔What Did I Struggle With?

- did not think to use the modulo operator to maintain the circular array

💡 Explanation of Solution

for k == 0, return a new array of size n with all values equal to 0
for k > 0, itearte from 1 to k and calculate (i + j) % n to sum the next k elements
for k < 0, iterate from 1 to abs(k) and calculate (i-j+n) % n to sum the previous k elements
handle negative modulo by adding n before applying %n to ensure positive indicies

⌛ Complexity Analysis

Time Complexity: O(n * k) 
- for every element of n, we traversing k elements ahead or behind to calculate the sum

Space Complexity: O(n)
- additional n space is used for the results vector
- this is somewhat a requirement of the problem since it states that all elements must be changed "at once" which I translated as returning a new vector with all correct elements already in place

💻 Implementation of Solution

class Solution {
public:
	vector<int> decrypt(vector<int>& code, int k) {
		int n = code.size();
		vector<int> result(n,0);
 
		if(k == 0) return result;
 
		for(int i=0; i < n; i++) {
			if(k > 0) {
				// sum the next k elements
				for(int j = 1; j <= k; j++)
					result[i] += code[(i+j) % n];
			}
			else if (k < 0) {
				// sum the previous k elements
				for(int j = 1; j <= abs(k); j++)
					result[i] += code[(i-j+n) % n];
			}
		}
		return result;
	}
};