Daily DSA: Light Switch Board (Medium)
Advertisement
Problem Statement
You are managing a long hallway with n light bulbs, indexed 0 to n - 1. Initially, all bulbs are turned off (0).
You need to process q queries of two types:
- Toggle Range (
1 left right): For every bulbiwhereleft <= i <= right, flip its state. If the bulb was off, it becomes on; if it was on, it becomes off. - Count On (
2 left right): Return the number of bulbs that are currently on in the inclusive range[left, right].
Examples
Example 1:
Input:
n = 5
queries = [[1, 0, 2], [2, 0, 4], [1, 2, 4], [2, 0, 4]]
Output:
[3, 4]
Explanation:
- Initial state:
[OFF, OFF, OFF, OFF, OFF] 1 0 2: Toggle bulbs 0, 1, and 2. State:[ON, ON, ON, OFF, OFF]2 0 4: Count ON bulbs in[0, 4]. Indices 0, 1, 2 are ON. Result:3.1 2 4: Toggle bulbs 2, 3, and 4. Bulb 2 turns OFF, bulbs 3 and 4 turn ON. State:[ON, ON, OFF, ON, ON]2 0 4: Count ON bulbs in[0, 4]. Indices 0, 1, 3, 4 are ON. Result:4.
Example 2:
Input:
n = 10, queries = [[1, 0, 9], [2, 0, 9], [1, 5, 5], [2, 0, 9]]
Output:
[10, 9]
Explanation:
1 0 9: All 10 bulbs turn ON.2 0 9: Count is 10.1 5 5: Bulb 5 turns OFF.2 0 9: Count is 9.
Constraints
1 <= n <= 10^51 <= queries.length <= 10^5queries[i][0]is either1(Toggle) or2(Count).0 <= queries[i][1] <= queries[i][2] < n
Approach
A naive approach would take $O(N)$ for each toggle query, resulting in $O(N \cdot Q)$ total time, which is too slow for $10^5$.
We use a Segment Tree with Lazy Propagation to optimize range updates and queries to $O(\log N)$:
- Segment Tree Node: Each node in the tree stores
on_count, the number of bulbs currently ON in that node’s range. - Lazy Propagation: We maintain a boolean array
lazy. Iflazy[v]is true, it means the range covered by nodevneeds to be toggled, but the update hasn’t been pushed to its children yet. - Toggle Logic: When we toggle a range $[L, R]$:
- If the current node’s range $[tl, tr]$ is entirely inside $[L, R]$, the new
on_countbecomes(tr - tl + 1) - on_count. We then flip thelazyflag for this node. - If there is a partial overlap, we push the current node’s lazy flag to its children and recurse.
- If the current node’s range $[tl, tr]$ is entirely inside $[L, R]$, the new
- Query Logic: Similar to standard range sum queries, we aggregate the
on_countfrom relevant nodes while pushing lazy flags down as needed.
C++ Solution
#include <vector>
#include <iostream>
using namespace std;
class LightSwitchBoard {
private:
int n;
vector<int> tree;
vector<bool> lazy;
void push(int v, int tl, int tr) {
if (lazy[v]) {
int tm = tl + (tr - tl) / 2;
// Toggle left child
tree[2 * v] = (tm - tl + 1) - tree[2 * v];
lazy[2 * v] = !lazy[2 * v];
// Toggle right child
tree[2 * v + 1] = (tr - tm) - tree[2 * v + 1];
lazy[2 * v + 1] = !lazy[2 * v + 1];
lazy[v] = false;
}
}
void update(int v, int tl, int tr, int l, int r) {
if (l > r) return;
if (l == tl && r == tr) {
tree[v] = (tr - tl + 1) - tree[v];
lazy[v] = !lazy[v];
} else {
push(v, tl, tr);
int tm = tl + (tr - tl) / 2;
update(2 * v, tl, tm, l, min(r, tm));
update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}
int query(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (l == tl && r == tr) return tree[v];
push(v, tl, tr);
int tm = tl + (tr - tl) / 2;
return query(2 * v, tl, tm, l, min(r, tm)) +
query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}
public:
LightSwitchBoard(int n) : n(n) {
tree.assign(4 * n, 0);
lazy.assign(4 * n, false);
}
void toggle(int l, int r) {
update(1, 0, n - 1, l, r);
}
int countOn(int l, int r) {
return query(1, 0, n - 1, l, r);
}
};
vector<int> processQueries(int n, vector<vector<int>>& queries) {
LightSwitchBoard lsb(n);
vector<int> results;
for (auto& q : queries) {
if (q[0] == 1) {
lsb.toggle(q[1], q[2]);
} else {
results.push_back(lsb.countOn(q[1], q[2]));
}
}
return results;
}
Complexity Analysis
- Time Complexity: $O((N + Q) \log N)$. Building the tree (implicitly) takes $O(N)$, and each of the $Q$ queries takes $O(\log N)$ due to the segment tree structure.
- Space Complexity: $O(N)$ to store the segment tree and lazy propagation arrays (typically $4N$ nodes).
Advertisement