Points That Intersect With Cars

Solution

Java Code

class Solution {
    public int numberOfPoints(List<List<Integer>> nums) {
        int[] prefixSum = new int[102];
        for(List<Integer> num : nums) {
            int left = num.get(0);
            int right = num.get(1);
            prefixSum[left] += 1;
            prefixSum[right + 1] -= 1;
        }

        int count = 0;
        for(int i = 1; i < 102; i++) {
            prefixSum[i] = prefixSum[i - 1] + prefixSum[i];
            if(prefixSum[i] > 0) {
                count += 1;
            }
        }
        return count;
    }
}

C++ Code

#include <vector>
using namespace std;

class Solution {
public:
    int numberOfPoints(vector<vector<int>>& nums) {
        vector<int> prefixSum(102, 0);
        
        for (auto& num : nums) {
            int left = num[0];
            int right = num[1];
            prefixSum[left] += 1;
            prefixSum[right + 1] -= 1;
        }
        
        int count = 0;
        for (int i = 1; i < 102; i++) {
            prefixSum[i] = prefixSum[i - 1] + prefixSum[i];
            if (prefixSum[i] > 0) {
                count += 1;
            }
        }
        
        return count;
    }
};

Python Code

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        prefix_sum = [0] * 102 
        
        for left, right in nums:
            prefix_sum[left] += 1
            prefix_sum[right + 1] -= 1
        
        count = 0
        for i in range(1, 102):
            prefix_sum[i] = prefix_sum[i - 1] + prefix_sum[i]
            if prefix_sum[i] > 0:
                count += 1
        
        return count

The reason we have taken a fixed array of the size is because, as per the constraints, the maximum value of range number can be 100. Now, suppose we are given a range [20, 100], that means we need 101 index to update and if we need 101 index then the size should be 102.

Complexity Analysis

Time Complexity: O(N + Q), where N is the size of the prefixSum array and Q is the number of queries represented by nums array.
Space Complexity: O(N), the size of the prefixSum array.