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.

Points That Intersect With Cars — LeetCode 2848 Python Solution

EasyArrayHash TablePrefix Sum

Problem: #2848
Pattern: 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

Python

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

Measure	Complexity
Time	O(n + m)
Space	O(m), where n is the length of the given array, and m is the maximum value in the array auxiliary

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.

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.