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¶
"""
- Merge all overlapping intervals.
<iframe width="560" height="315" src="https://www.youtube.com/embed/44H3cEC2fFM?si=J-Jr_Fg2eDse3-de" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
"""
from typing import List
# Intervals
def merge(intervals: List[List[int]]) -> List[List[int]]:
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 👑¶
"""
- Given an array of meeting time `intervals` where `intervals[i] = [start_i, end_i]`, return the minimum number of conference rooms required.
"""
import heapq
from typing import List
# Heap
def minMeetingRooms(intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[0])
minHeap = [intervals[0][1]]
for i in range(1, len(intervals)):
if intervals[i][0] >= minHeap[0]:
heapq.heappop(minHeap)
heapq.heappush(minHeap, intervals[i][1])
return len(minHeap)
if __name__ == "__main__":
intervals = [[0, 30], [5, 10], [15, 20]]
assert minMeetingRooms(intervals) == 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]