Maximum White Tiles Covered by a Carpet - Practice Coding Problems

Maximum White Tiles Covered by a Carpet - Problem

Array Binary Search Greedy Sliding Window Sorting Prefix Sum Medium

You are given a 2D integer array tiles where tiles[i] = [li, ri] represents that every tile j in the range li <= j <= ri is colored white.

You are also given an integer carpetLen, the length of a single carpet that can be placed anywhere.

Return the maximum number of white tiles that can be covered by the carpet.

Input & Output

Example 1 — Basic Case

$ Input: tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10

› Output: 9

💡 Note: Place carpet from position 10 to 19. It covers tiles [10,11] (2 tiles), [12,18] (7 tiles), totaling 9 tiles.

Example 2 — Optimal Positioning

$ Input: tiles = [[10,11],[1,1]], carpetLen = 2

› Output: 2

💡 Note: Place carpet from position 10 to 11, covering both tiles [10,11] completely for 2 tiles total.

Example 3 — Single Large Range

$ Input: tiles = [[1,100]], carpetLen = 10

› Output: 10

💡 Note: The carpet can cover at most 10 consecutive positions from the range [1,100].

Constraints

1 ≤ tiles.length ≤ 5 × 10⁴
tiles[i].length == 2
1 ≤ l_i ≤ r_i ≤ 10⁹
1 ≤ carpetLen ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Tile ranges [[1,5],[10,11],[12,18]] and carpet length 10

Process

Find optimal carpet position to maximize tile coverage

Output

Maximum number of white tiles that can be covered: 9

Key Takeaway

🎯 Key Insight: Sort tiles by position and use sliding window to efficiently find the optimal carpet placement that maximizes white tile coverage.

Asked in

G Google 12 M Microsoft 8 a Amazon 6

The key insight is to recognize this as an optimal interval coverage problem. Sort the tile ranges and use sliding window technique to efficiently find the carpet position that maximizes coverage. The sliding window approach gives us O(n log n) time complexity by avoiding redundant calculations. Best approach: sliding-window with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n × m)	O(1)	Try every possible carpet position and count covered tiles
Prefix Sum with Binary Search	O(n log n + m log m)	O(m)	Use prefix sums and binary search for optimal range query performance
Sliding Window with Sorting	O(n log n)	O(1)	Sort tiles and use sliding window to find optimal carpet placement

Brute Force — Algorithm Steps

Step 1: Generate all possible carpet positions
Step 2: For each position, count covered tiles
Step 3: Return maximum count

Visualization

Tap to expand

Step-by-Step Walkthrough

Input

Tile ranges and carpet length

Try Positions

Test carpet at each position

Count Coverage

Find position with maximum tiles covered

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int tiles[][2], int tilesSize, int carpetLen) {
    if (tilesSize == 0) return 0;
    
    // Find the range of all possible positions
    int minPos = INT_MAX, maxPos = INT_MIN;
    for (int i = 0; i < tilesSize; i++) {
        if (tiles[i][0] < minPos) minPos = tiles[i][0];
        if (tiles[i][1] > maxPos) maxPos = tiles[i][1];
    }
    
    int maxCovered = 0;
    
    // Try every possible carpet starting position
    for (int start = minPos; start <= maxPos; start++) {
        int carpetEnd = start + carpetLen - 1;
        int covered = 0;
        
        // Count tiles covered by carpet at this position
        for (int i = 0; i < tilesSize; i++) {
            int left = tiles[i][0], right = tiles[i][1];
            // Calculate overlap between tile range and carpet
            int overlapStart = (start > left) ? start : left;
            int overlapEnd = (carpetEnd < right) ? carpetEnd : right;
            if (overlapStart <= overlapEnd) {
                covered += overlapEnd - overlapStart + 1;
            }
        }
        
        if (covered > maxCovered) {
            maxCovered = covered;
        }
    }
    
    return maxCovered;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse tiles array (simplified parsing)
    int tiles[1000][2];
    int tilesSize = 0;
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            tiles[tilesSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            tiles[tilesSize][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            tilesSize++;
        }
        ptr++;
    }
    
    int carpetLen;
    scanf("%d", &carpetLen);
    
    printf("%d\n", solution(tiles, tilesSize, carpetLen));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

For each of m possible positions, we check all n tile ranges

✓ Linear Growth

Space Complexity

O(1)

Only using variables for counting, no extra data structures

✓ Linear Space

31.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler