Points That Intersect With Cars

Easy
567.

Points That Intersect With Cars

Points That Intersect With Cars is an easy coding problem on arrays and prefix sum, asked in Amazon and TCS interviews.

You are given a 2D array nums where nums[i] = [start, end] means the i-th car is parked on the integer points from start to end, inclusive.

Return the number of integer points covered by any part of a car.

Example 1

Input
nums = [[3,6],[1,5],[4,7]]
Output
7
Explanation
Points 1 through 7 are all covered.

Example 2

Input
nums = [[1,3],[5,8]]
Output
7
Explanation
Points 1,2,3 and 5,6,7,8.

Example 3

Input
nums = [[2,2]]
Output
1

Constraints

  • 1 <= nums.length <= 100
  • nums[i].length == 2
  • 1 <= start <= end <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} nums
 * @return {number}
 */
var numberOfPoints = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Points That Intersect With Cars — Problem & Solution

Points That Intersect With Cars solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Points That Intersect With Cars is an easy coding problem on arrays and prefix sum, asked in Amazon and TCS interviews.

  • Difficulty: Easy
  • Topics: Arrays, Prefix Sum
  • Asked at: Amazon, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a 2D array nums where nums[i] = [start, end] means the i-th car is parked on the integer points from start to end, inclusive.

Return the number of integer points covered by any part of a car.

Example 1

Input: nums = [[3,6],[1,5],[4,7]]
Output: 7
Explanation: Points 1 through 7 are all covered.

Example 2

Input: nums = [[1,3],[5,8]]
Output: 7
Explanation: Points 1,2,3 and 5,6,7,8.

Example 3

Input: nums = [[2,2]]
Output: 1

Constraints

  • 1 <= nums.length <= 100
  • nums[i].length == 2
  • 1 <= start <= end <= 100

Hints for Points That Intersect With Cars

  1. Hint 1

    Coordinates only go up to 100, so a boolean array over the points is plenty.

  2. Hint 2

    Mark every point of every car, then count the marks.

  3. Hint 3

    A difference array works too and generalises to much larger coordinates.

How to solve Points That Intersect With Cars

The coordinate space is tiny, so marking covered points directly and counting them is both simplest and fastest here.

Approach

  1. Create a set (or a 101-slot boolean array) of covered points.
  2. For each car, mark every point from start to end inclusive.
  3. Return the number of distinct marked points.

Why it works

Marking is idempotent, so overlapping cars are naturally deduplicated — which is exactly what "covered by any car" means.

Complexity

  • Time — O(n · L) where L is the coordinate range
  • Space — O(L)

Pitfalls

  • Summing the interval lengths double-counts overlaps.
  • The range is inclusive at both ends, so the loop bound is <= end.
  • For a much larger coordinate range, sort-and-merge or a difference array is the right tool.

Reference solution

Python

from typing import List

def numberOfPoints(nums: List[List[int]]) -> int:
    covered = set()
    for s, e in nums:
        for p in range(s, e + 1):
            covered.add(p)
    return len(covered)

Java

public static int numberOfPoints(int[][] nums) {
    boolean[] covered = new boolean[102];
    for (int[] car : nums) {
        for (int p = car[0]; p <= car[1]; p++) covered[p] = true;
    }
    int count = 0;
    for (boolean c : covered) if (c) count++;
    return count;
}

C++

int numberOfPoints(vector<vector<int>>& nums) {
    vector<bool> covered(102, false);
    for (auto& car : nums) {
        for (int p = car[0]; p <= car[1]; p++) covered[p] = true;
    }
    int count = 0;
    for (int p = 0; p < 102; p++) if (covered[p]) count++;
    return count;
}

JavaScript

var numberOfPoints = function(nums) {
    const covered = new Array(102).fill(false);
    for (let i = 0; i < nums.length; i++) {
        for (let p = nums[i][0]; p <= nums[i][1]; p++) covered[p] = true;
    }
    let count = 0;
    for (let p = 0; p < covered.length; p++) if (covered[p]) count++;
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum