EasyNo. 2848
Points That Intersect With Cars — LeetCode 2848 Python Solution
- Pattern
- Prefix Sum
- Topics
- Array, Hash Table, Prefix Sum
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a 0-indexed 2D integer array nums representing the coordinates of the cars parking on a number line. For any index i, nums[i] = [starti, endi] where starti is the starting point of the ith car and endi is the ending point of the ith car.
Example
- Input
- nums = [[3,6],[1,5],[4,7]]
- Output
- 7
- Explanation
- All the points from 1 to 7 intersect at least one car, therefore the answer would be 7.
Python solution
class Solution:
def numberOfPoints(self, nums: List[List[int]]) -> int:
m = 102
d = [0] * m
for start, end in nums:
d[start] += 1
d[end + 1] -= 1
return sum(s > 0 for s in accumulate(d))Complexity
- Time
- O(n + m)
- Space · auxiliary
- O(m)where n is the length of the given array, and m is the maximum value in the array
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 2848. Points That Intersect With Cars is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2845 | Count of Interesting Subarrays | Medium |
| 0523 | Continuous Subarray Sum | Medium |
| 0525 | Contiguous Array | Medium |
| 0560 | Subarray Sum Equals K | Medium |
| 0930 | Binary Subarrays With Sum | Medium |
| 0974 | Subarray Sums Divisible by K | Medium |
Frequently asked questions
- How hard is LeetCode 2848. Points That Intersect With Cars?
LeetCode 2848. Points That Intersect With Cars is rated Easy on LeetCode.
- What is the time complexity of LeetCode 2848. Points That Intersect With Cars?
The Python solution on this page runs in O(n + m).
- What is the space complexity of LeetCode 2848. Points That Intersect With Cars?
The Python solution on this page uses O(m), where n is the length of the given array, and m is the maximum value in the array auxiliary space.
- What topics does LeetCode 2848. Points That Intersect With Cars cover?
LeetCode 2848. Points That Intersect With Cars is tagged Array, Hash Table and Prefix Sum on LeetCode.