Leetcode 2848: Points That Intersect With Cars
You are given a list of cars represented by their starting and ending positions on a number line. Your task is to count how many distinct integer points are covered by any part of a car.
Problem
Approach
Steps
Complexity
Input: A list of pairs representing the start and end positions of each car on the number line.
Example: nums = [[1, 4], [2, 5], [6, 7]]
Constraints:
• 1 <= nums.length <= 100
• nums[i].length == 2
• 1 <= starti <= endi <= 100
Output: The total number of distinct integer points covered by any part of a car.
Example: Output: 6
Constraints:
• The output should be a single integer representing the total number of distinct integer points.
Goal: Find the total number of distinct integer points covered by any part of a car.
Steps:
• Create a boolean array to represent the points on the number line that are covered by a car.
• For each car, mark the points it covers as true in the array.
• Count the number of true values in the array, which represents the total number of covered points.
Goal: The constraints on the input values for the problem.
Steps:
• 1 <= nums.length <= 100
• nums[i].length == 2
• 1 <= starti <= endi <= 100
Assumptions:
• All cars have valid starting and ending positions where starti <= endi.
• The cars may overlap, but each point on the number line is counted only once.
• Input: nums = [[1, 4], [2, 5], [6, 7]]
• Explanation: The integer points covered by the cars are: 1, 2, 3, 4, 5, 6. Hence, the total number of points covered is 6.
• Input: nums = [[1, 3], [4, 6], [5, 8]]
• Explanation: The integer points covered by the cars are: 1, 2, 3, 4, 5, 6, 7, 8. After removing duplicates, the answer is 6.
Approach: The approach involves creating an array to mark the covered integer points and then counting how many distinct points are covered by any of the cars.
Observations:
• We need to track the integer points on the number line covered by the cars.
• The positions of the cars may overlap, so we need to count each point only once.
• We can use a boolean array to mark covered points and count the true values to find the answer.
Steps:
• Create a boolean array of size 101 to mark the covered integer points (since starti and endi are between 1 and 100).
• Iterate over each car and mark the corresponding points as true.
• Finally, count how many points in the array are true, and return the count.
Empty Inputs:
• No empty input arrays are expected as per the problem statement.
Large Inputs:
• The solution should handle the maximum number of cars efficiently.
Special Values:
• Cars with the same start and end position should still be counted correctly.
Constraints:
• The approach should work within the time and space constraints provided.
int numberOfPoints(vector<vector<int>>& nums) {
vector<int> v(102, 0);
int ans = 0;
for(auto n: nums){
for(int i = n[0]; i <= n[1]; ++i) v[i-1]++;
}
for(auto e: v){
if(e) ans++;
}
return ans;
}
1 : Function Declaration
int numberOfPoints(vector<vector<int>>& nums) {
Defines the function 'numberOfPoints', which takes a vector of integer pairs as input representing ranges.
2 : Vector Initialization
vector<int> v(102, 0);
Initializes a vector 'v' of size 102 to track the frequency of each point in the range, all initialized to zero.
3 : Variable Initialization
int ans = 0;
Declares and initializes an integer variable 'ans' to store the count of distinct points covered by the ranges.
4 : Outer Loop
for(auto n: nums){
Starts a loop to iterate over each range in the input vector 'nums'. Each range is represented by a pair of integers.
5 : Inner Loop
for(int i = n[0]; i <= n[1]; ++i) v[i-1]++;
For each range, this loop increments the corresponding index in the vector 'v' for each point between the range's start and end (inclusive).
6 : Count Points
for(auto e: v){
Starts a loop to iterate over the elements of the vector 'v' to count how many distinct points are covered.
7 : Condition Check
if(e) ans++;
Increments 'ans' whenever a point is covered (i.e., the count at that index is greater than zero).
8 : Return Statement
return ans;
Returns the total count of distinct points covered by the ranges.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) where n is the number of cars, as we iterate over each car and the points it covers.
Best Case: O(101)
Worst Case: O(101)
Description: The space complexity is O(101) because we use an array of size 101 to track covered points.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus