Skip to main content
Talentd

Maximum White Tiles Covered by a Carpet - Solution & Explanation

MediumArrayBinary SearchGreedySorting8 min readAsked at: Amazon, Google, Lti
Practice this problem

Problem Statement

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.

 

Example 1:

Input: tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
Output: 9
Explanation: Place the carpet starting on tile 10. 
It covers 9 white tiles, so we return 9.
Note that there may be other places where the carpet covers 9 white tiles.
It can be shown that the carpet cannot cover more than 9 white tiles.

Example 2:

Input: tiles = [[10,11],[1,1]], carpetLen = 2
Output: 2
Explanation: Place the carpet starting on tile 10. 
It covers 2 white tiles, so we return 2.

 

Constraints:

  • 1 <= tiles.length <= 5 * 104
  • tiles[i].length == 2
  • 1 <= li <= ri <= 109
  • 1 <= carpetLen <= 109
  • The tiles are non-overlapping.

Approach Overview

Problem Overview: You receive several intervals representing white tiles on a floor and a carpet of fixed length. The goal is to place the carpet so it covers the maximum number of white tiles. Intervals may be far apart, so the solution must account for both fully covered tiles and partially covered segments.

Approach 1: Prefix Array with Sliding Window (O(n log n) time, O(n) space)

Start by sorting the tile intervals by their starting position using sorting. Build a prefix array where each entry stores the cumulative count of white tiles up to that interval. For each interval i, treat its start as the carpet's left boundary and compute the carpet's right boundary start + carpetLen - 1. Use binary search to find the last interval that lies fully within this range. The prefix array instantly gives the number of tiles covered by complete intervals, while a small adjustment handles the partially covered interval at the boundary. This approach is reliable and easy to reason about because the prefix array avoids repeatedly summing tile lengths.

Approach 2: Two-Pointer Technique (O(n) time after sorting, O(1) extra space)

This method treats the intervals like a sliding window over a sorted array. Maintain two pointers: left marks the first interval currently under consideration and right expands the window while intervals remain fully covered by the carpet starting at tiles[left][0]. As the window expands, accumulate the total number of fully covered tiles. If the next interval extends beyond the carpet's limit, compute the partial coverage of that interval and update the maximum result. When the window moves forward, subtract the tile length at left and advance the pointer. Each interval enters and leaves the window once, producing a linear scan after sorting. The technique follows a classic greedy sliding window pattern where coverage is maximized locally.

Recommended for interviews: Interviewers usually expect the sliding window or two-pointer solution. It demonstrates strong understanding of interval processing, greedy reasoning, and window management. Starting with the prefix + binary search method shows structured thinking, while the optimized two-pointer technique highlights deeper algorithmic skill and achieves near-linear runtime.

Approach 1: Prefix Array with Sliding Window

This approach involves sorting the tiles by their starting position and then using a prefix sum array to store the cumulative white tiles covered up to each position. By simulating placing the carpet at several positions using a sliding window technique, we can efficiently determine the maximum coverage.

The solution sorts the tiles first and maintains a prefix sum array to track cumulative tile coverage. It uses a sliding window approach to simulate placing the carpet starting at each tile beginning, calculating the covered tiles using the prefix sum, and adjusting for partial overlaps.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of tile blocks. Space Complexity: O(n) for the prefix array.

Try this approach in the editor →

Approach 2: Two-Pointer Technique

The two-pointer method efficiently handles finding maximum coverage by using one pointer to denote the start of the carpet and another to extend it. By iterating over possible start positions and adjusting the end position based on carpet length, the maximum coverage is determined dynamically.

This C++ solution employs a two-pointer method where the starting point of the carpet is fixed, and the end is dynamically adjusted based on the length. The initial pointer uses inner loops to calculate coverage while the outer loop progresses the starting point.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n log n) due to sorting tiles, and Space Complexity: O(1), meaning memory usage does not scale with input size.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Array with Sliding Window

Time Complexity: O(n log n) due to sorting, where n is the number of tile blocks. Space Complexity: O(n) for the prefix array.

Two-Pointer Technique

Time Complexity: O(n log n) due to sorting tiles, and Space Complexity: O(1), meaning memory usage does not scale with input size.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix Array + Binary Search Sliding WindowO(n log n)O(n)When you want a clear interval coverage calculation using prefix sums and binary search
Two-Pointer TechniqueO(n) after sortingO(1)Best for interviews and optimal performance with a greedy sliding window

Video Solution

Maximum White Tiles Covered by a Carpet | 2271 LeetCode| Binary Search |Leetcode Biweekly Contest 78 • CodeWithSunny • 4,120 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Maximum White Tiles Covered by a Carpet easy or hard?
Maximum White Tiles Covered by a Carpet is classified as a Medium problem on LeetCode. The difficulty comes from correctly handling partially covered intervals and choosing an efficient sliding window or prefix-based strategy.
Maximum White Tiles Covered by a Carpet Python/Java solution
Python implementations commonly use prefix sums with binary search or a sliding window loop over sorted intervals. Java solutions often implement the two-pointer approach with variables tracking the current window coverage and partial overlaps.
How to solve Maximum White Tiles Covered by a Carpet in O(n)?
After sorting the tile intervals, use a two-pointer sliding window. Expand the right pointer while intervals remain fully covered by the carpet starting at the left interval. Track the sum of covered tile lengths and compute partial coverage when the carpet overlaps only part of the next interval.
What is the best approach for Maximum White Tiles Covered by a Carpet?
The two-pointer sliding window approach is typically the best solution. After sorting the tile intervals, maintain a window of intervals fully covered by the carpet and calculate partial coverage when the boundary cuts through a tile. This runs in O(n) time after sorting and uses O(1) extra space.
Is Maximum White Tiles Covered by a Carpet asked at Google/Amazon/Meta?
Interval coverage and sliding window problems like this appear frequently in interviews at companies such as Amazon, Google, and Meta. The problem tests sorting, greedy reasoning, and efficient window management across interval ranges.
What data structure is used in Maximum White Tiles Covered by a Carpet?
The solution primarily uses arrays of intervals combined with sorting and sliding window pointers. Some implementations also use prefix sum arrays and binary search to quickly compute how many tiles are fully covered within a range.
What is the time complexity of Maximum White Tiles Covered by a Carpet?
The optimal algorithm runs in O(n log n) time overall because the intervals must be sorted first. After sorting, the sliding window or two-pointer scan processes each interval once, which takes O(n). Space complexity ranges from O(1) to O(n) depending on whether prefix arrays are used.

Ready to solve this problem?

Practice Maximum White Tiles Covered by a Carpet with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Number of Vowels in a Substring of Given Length