1D Difference Array¶
Table of Contents¶
- 2848. Points That Intersect With Cars (Easy)
- 1893. Check if All the Integers in a Range Are Covered (Easy)
- 1854. Maximum Population Year (Easy)
- 2960. Count Tested Devices After Test Operations (Easy)
- 1094. Car Pooling (Medium)
- 1109. Corporate Flight Bookings (Medium)
- 3355. Zero Array Transformation I (Medium)
- 56. Merge Intervals (Medium)
- 57. Insert Interval (Medium)
- 732. My Calendar III (Hard)
- 2406. Divide Intervals Into Minimum Number of Groups (Medium)
- 2381. Shifting Letters II (Medium)
- 3453. Separate Squares I (Medium)
- 995. Minimum Number of K Consecutive Bit Flips (Hard)
- 1589. Maximum Sum Obtained of Any Permutation (Medium)
- 1526. Minimum Number of Increments on Subarrays to Form a Target Array (Hard)
- 3356. Zero Array Transformation II (Medium)
- 1943. Describe the Painting (Medium)
- 3224. Minimum Array Changes to Make Differences Equal (Medium)
- 2251. Number of Flowers in Full Bloom (Hard)
- 2772. Apply Operations to Make All Array Elements Equal to Zero (Medium)
- 3229. Minimum Operations to Make Array Equal to Target (Hard)
- 798. Smallest Rotation with Highest Score (Hard)
- 3347. Maximum Frequency of an Element After Performing Operations II (Hard)
- 2528. Maximize the Minimum Powered City (Hard)
- 1674. Minimum Moves to Make Array Complementary (Medium)
- 3362. Zero Array Transformation III (Medium)
- 3017. Count the Number of Houses at a Certain Distance II (Hard)
- 253. Meeting Rooms II (Medium) 👑
- 370. Range Addition (Medium) 👑
- 1989. Maximum Number of People That Can Be Caught in Tag (Medium) 👑
- 759. Employee Free Time (Hard) 👑
- 2021. Brightest Position on Street (Medium) 👑
- 2015. Average Height of Buildings in Each Segment (Medium) 👑
- 2237. Count Positions on Street With Required Brightness (Medium) 👑
- 3009. Maximum Number of Intersections on the Chart (Hard) 👑
- 3279. Maximum Total Area Occupied by Pistons (Hard) 👑
2848. Points That Intersect With Cars¶
"""
- Return the number of points that intersect with cars.
"""
from itertools import accumulate
from typing import List
# Differnce Array
def numberOfPoints(nums: List[List[int]]) -> int:
max_end = max(end for _, end in nums)
diff = [0] * (max_end + 2)
for start, end in nums:
diff[start] += 1
diff[end + 1] -= 1
return sum(s > 0 for s in accumulate(diff))
nums = [[3, 6], [1, 5], [4, 7]]
print(numberOfPoints(nums)) # 7
1893. Check if All the Integers in a Range Are Covered¶
1854. Maximum Population Year¶
2960. Count Tested Devices After Test Operations¶
1094. Car Pooling¶
"""
- Return `False` if the total number of passengers at any point is greater than `capacity`. Otherwise, return `True`.
"""
from itertools import accumulate
from typing import List
# Difference Array
def carPooling1(trips: List[List[int]], capacity: int) -> bool:
max_location = 0
for trip in trips:
max_location = max(max_location, trip[2])
diff = [0] * (max_location + 1)
n = len(diff)
for num, start, end in trips:
diff[start] += num
if end < n:
diff[end] -= num
cur = 0
for i in range(n):
cur += diff[i]
if cur > capacity:
return False
return True
# Difference Array
def carPooling2(trips: List[List[int]], capacity: int) -> bool:
diff = [0] * 1001
for num, start, end in trips:
diff[start] += num
diff[end] -= num
return all(s <= capacity for s in accumulate(diff))
trips = [[2, 1, 5], [3, 3, 7]]
capacity = 4
print(carPooling1(trips, capacity)) # False
print(carPooling2(trips, capacity)) # False
1109. Corporate Flight Bookings¶
"""
- Return the number of seats booked on each flight.
"""
from typing import List
# Difference Array
def corpFlightBookings(bookings: List[List[int]], n: int) -> List[int]:
"""Return the number of seats booked for each flight."""
res = [0 for _ in range(n)]
for i, j, k in bookings:
res[i - 1] += k
if j < n:
res[j] -= k
for i in range(1, n):
res[i] += res[i - 1]
return res
bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]]
n = 5
print(corpFlightBookings(bookings, n)) # [10, 55, 45, 25, 25]
3355. Zero Array Transformation I¶
56. Merge Intervals¶
def merge(intervals: list[list[int]]) -> list[list[int]]:
"""
Merge all overlapping intervals.
| G----H
| E===========F
| C--------D
| A========B
|
|-----------------------------------
Draw the above to explain the process to the interviewer.
Time complexity: O(nlogn) due to sorting.
Space complexity: O(n) for the result list.
"""
n = len(intervals)
if n <= 1:
return intervals
intervals.sort(key=lambda x: x[0])
res = [intervals[0]]
for i in range(1, n):
if intervals[i][0] <= res[-1][1]:
res[-1][1] = max(res[-1][1], intervals[i][1])
else:
res.append(intervals[i])
return res
print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// Interval
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto& range : intervals) {
if (!res.empty() && range[0] <= res.back()[1]) {
res.back()[1] = max(res.back()[1], range[1]);
} else {
res.emplace_back(range);
}
}
return res;
}
int main() {
vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
vector<vector<int>> res = merge(intervals);
for (auto& range : res) {
cout << range[0] << ", " << range[1] << endl;
}
return 0;
}
57. Insert Interval¶
from typing import List
# Interval
def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
n = len(intervals)
if n == 0:
return [newInterval]
if newInterval[1] < intervals[0][0]:
return [newInterval] + intervals
if newInterval[0] > intervals[-1][1]:
return intervals + [newInterval]
i = 0
result = []
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
while i < n:
result.append(intervals[i])
i += 1
return result
intervals = [[1, 3], [6, 9]]
newInterval = [2, 5]
print(insert(intervals, newInterval)) # [[1, 5], [6, 9]]
732. My Calendar III¶
2406. Divide Intervals Into Minimum Number of Groups¶
2381. Shifting Letters II¶
3453. Separate Squares I¶
995. Minimum Number of K Consecutive Bit Flips¶
1589. Maximum Sum Obtained of Any Permutation¶
from typing import List
# Greedy
def maxSumRangeQuery(nums: List[int], requests: List[List[int]]) -> int:
n = len(nums)
freq = [0 for _ in range(n + 1)]
for start, end in requests:
freq[start] += 1
if end + 1 < n:
freq[end + 1] -= 1
for i in range(1, n):
freq[i] += freq[i - 1]
freq.pop()
freq.sort(reverse=True)
nums.sort(reverse=True)
max_sum = 0
mod = 10**9 + 7
for i, j in zip(nums, freq):
max_sum += i * j
max_sum %= mod
return max_sum
nums = [1, 2, 3, 4, 5]
requests = [[1, 3], [0, 1]]
print(maxSumRangeQuery(nums, requests)) # 19
1526. Minimum Number of Increments on Subarrays to Form a Target Array¶
3356. Zero Array Transformation II¶
1943. Describe the Painting¶
3224. Minimum Array Changes to Make Differences Equal¶
2251. Number of Flowers in Full Bloom¶
2772. Apply Operations to Make All Array Elements Equal to Zero¶
3229. Minimum Operations to Make Array Equal to Target¶
798. Smallest Rotation with Highest Score¶
3347. Maximum Frequency of an Element After Performing Operations II¶
2528. Maximize the Minimum Powered City¶
1674. Minimum Moves to Make Array Complementary¶
3362. Zero Array Transformation III¶
3017. Count the Number of Houses at a Certain Distance II¶
253. Meeting Rooms II 👑¶
from heapq import heappop, heappush
from typing import List
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
"""Min Heap: O(n log n) time, O(n) space.
Track active meeting end times; the peak heap size is the minimum
number of rooms required.
Timeline (letters mark meeting endpoints):
| G----H
| E-----------F
| C--------------D
| A----------B
+----------------------------------
Heap simulation (earliest end first):
A: push B -> [B]
C: C < B, push D -> [B, D]
E: pop B and D, push F -> [F]
G: G < F, push H -> [H, F]
The peak heap size is 2, so two rooms are required.
"""
ends = []
res = 0
for start, end in sorted(intervals):
while ends and ends[0] <= start:
heappop(ends)
heappush(ends, end)
res = max(res, len(ends))
return res
def test_min_meeting_rooms():
s = Solution()
for fn in (s.minMeetingRooms,):
assert fn([]) == 0
assert fn([[0, 30], [5, 10], [15, 20]]) == 2
assert fn([[7, 10], [2, 4]]) == 1
assert fn([[1, 5], [5, 10], [5, 8]]) == 2
370. Range Addition 👑¶
from typing import List
def getModifiedArray(length: int, updates: List[List[int]]) -> List[int]:
"""
Return the final array after applying all the Adition operations.
method: difference array
"""
res = [0 for _ in range(length)]
for start, end, inc in updates:
res[start] += inc
if end + 1 < length:
res[end + 1] -= inc
for i in range(1, length):
res[i] += res[i - 1]
return res
if __name__ == "__main__":
length = 5
updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]]
assert getModifiedArray(length, updates) == [-2, 0, 3, 5, 3]