Wifi Range

Time: O(n)

Space: O(1)

Intuition

Each router at position i covers a continuous interval [i-x, i+x] after clamping to the road boundaries. If the union of all router intervals covers every room from 0 to n-1 without gaps, then the WiFi range is sufficient. So this becomes an interval merge / coverage problem.

Algorithm

1Scan the string from left to right.
2For every router character "1" at position i, compute its coverage interval [max(0, i-x), min(n-1, i+x)].
3Keep a merged interval [l, r] for the coverage seen so far.
4If the first router is seen, initialise [l, r] with its interval.
5For later routers, if the new interval starts after a gap from r, return false.
6Otherwise extend the merged interval with min(l, lx) and max(r, ry).
7At the end, return true only if [l, r] spans the whole road.

Example Walkthrough

Input: s = "1000101", x = 1

1.Router at 0 covers [0,1].
2.Router at 4 covers [3,5]. There is a gap between 1 and 3.
3.Because coverage is not continuous, the answer is false.

Output: false

Common Pitfalls

•Clamp every router interval to the road bounds before merging.
•Touching intervals count as continuous coverage; only a gap larger than 1 breaks the range.
•Do not return true just because the first and last routers exist; the middle must also be covered.

Wifi Range.java

Java


// Approach: Build coverage intervals for every router as [i-x, i+x], clamp them to the road, and merge them.
// If any interval starts after a gap from the current merged range, coverage is broken.
// The road is fully covered only when the merged interval spans from the first to the last room.
// Time: O(n) Space: O(1)

class Solution {

    public boolean wifiRange(String s, int x) {
        int l = Integer.MAX_VALUE;
        int r = Integer.MIN_VALUE;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if (ch == '1') {
                int lx = i - x;
                if (lx < 0) {
                    lx = 0;
                }

                int ry = i + x;
                if (ry >= s.length()) {
                    ry = s.length() - 1;
                }

                // covers all rooms
                if (lx == 0 && ry == s.length() - 1) {
                    return true;
                }

                // first interval
                if (l == Integer.MAX_VALUE && r == Integer.MIN_VALUE) {
                    l = lx;
                    r = ry;
                } else {
                    // merge and check
                    if (lx > r && lx - r > 1) {
                        // gap found
                        return false;
                    }
                    // merge interval
                    l = Math.min(l, lx);
                    r = Math.max(r, ry);
                }
            }
        }

        return l == 0 && r == s.length() - 1;
    }
}

Was this solution helpful?