Pongal Bunk
Problem Description
Given a number N, which is the size of array where indices are from 1 to N . Initially all the elements of array are 0 . Q queries are given .
Each query contains two variables L and R . For each query you have to perform the following operation: for each index i where L<=i<=R you have to add a value of (i-L+1) to the array element at index i .
After performing Q queries, a number M is given. It is followed by M number of indices (I) where, for each index you have to output the value of element present in that index (I) of array.
Explanation
You are given an array of size N, initially filled with zeros. There are Q queries that update the array based on specified ranges. After processing all queries, you need to output the value of the array at specific indices.
Example
Input:
5 3
1 3
2 4
3 5
2
1
4
Output:
6
15
Explanation
The number of elements n is 5, and there are 3 queries.
The 1st query affects indices 1 to 3: ans[1] += 1, ans[2] += 2, ans[3] += 3
The 2nd query affects indices 2 to 4: ans[2] += 1, ans[3] += 2, ans[4] += 3
The 3rd query affects indices 3 to 5: ans[3] += 1, ans[4] += 2, ans[5] += 3
After processing the queries, the values in the ans array are:
ans[1] = 1
ans[2] = 3
ans[3] = 6
ans[4] = 10
ans[5] = 6
For the first index query: Querying index 1: ans[1] = 6
For the second index query: Querying index 4: ans[4] = 15
Constraints
- 1 <= N <= 1000000
- 1 <= Q <= 1000000
- 1 <= L <= R <= N
- 1 <= M <= N
We are given few queries with values of l and r and we are asked to alter the values between l and r with a certain value. So, why not trying iterating everytime from l to r and modify the values as mentioned. Let's check out how we can implement it!!
Brute Force Approach
Intuition
Imagine you have 5 empty boxes (numbered 1 to 5). We are given 3 instructions on how to add candies to these boxes. How many candies to the box ? It's (i-L+1). Here, L is the index from which we will add the candies into the box. If ,we simplify the above equation, we are told to add 1 candy to the Lth box, 2 candy to the (L+1)th box ,3 candies to (L+2)th box and so on.
In simple words, we are adding 1 extra candy to the current box to that of the previous box.
We need to start with boxes with initial values as [0, 0, 0, 0, 0]
Instruction 1: We are told to "Add candies from box 1 to box 3." Start at box 1 and add candies like this: We will add +1 to Box 1, then add
- Box 2: +2
- Box 3: +3
Now the boxes look like this: [1, 2, 3, 0, 0]
Instruction 2: We are again told to "Add candies from box 2 to box 4." So, we start at box 2 and add:
- Box 2: +1 → [1, 3, 3, 0, 0]
- Box 3: +2 → [1, 3, 5, 0, 0]
- Box 4: +3 → [1, 3, 5, 3, 0]
Instruction 3: Again we are asked to "Add candies from box 1 to box 5." So, starting at box 1 and add:
- Box 1: +1 → [2, 3, 5, 3, 0]
- Box 2: +2 → [2, 5, 5, 3, 0]
- Box 3: +3 → [2, 5, 8, 3, 0]
- Box 4: +4 → [2, 5, 8, 7, 0]
- Box 5: +5 → [2, 5, 8, 7, 5]
Now, we are asked to tell the number of candies in box 1, box 3 and box 5. We will simply look at the final array and tell the values present at 1st , 3rd and 5th indices which are 2, 8 and 5 respectively.
So , every time we get a new instruction, we walk from the starting box to the ending box and add candies step by step. Let's now see how we can code it up !
How is the input taken ?
First line contains an integer N indicating the size of array indexed from 1 to N.
Second line contains an integer Q denoting the number of Queries.
It is followed by Q number of lines where each line contains two space seperated integers L and R.
Next Line contains an Integer M denoting number of queries whose output is to be printed.
It is followed by M number of lines where each line contains an integer I (index of element in array).
How is the format for the output ?
For each of the M queries, output the value of element present in the array at index I.
Approach
Input Reading: Read n (number of elements) and q (number of queries). Initialize an array arr of size 1000002 with all elements set to 0.
Process Queries (q times): For each query:
Read l (left index) and r (right index).
For all indices j from l to r (inclusive): Increment arr[j] by (j - l + 1).
Handle Output: Read m (number of indices to query). While m is not zero:
Read indx (index to query). Print the value at arr[indx].
Dry-Run
n = 15 (size of array, not used in logic)
q = 3 (number of queries)
Queries:
1 5 3 8 6 10
m = 5 (number of indices to query)
Indices to query:
1
4
7
9
10
Output:
1 6 7 4 5
Initialization: arr[] is initialized with size 1000002 (all zeros).
1st Query: l = 1, r = 5
Loop j from 1 to 5:
- arr[1] += (1 - 1 + 1) = 1 → arr[1] = 1
- arr[2] += (2 - 1 + 1) = 2 → arr[2] = 2
- arr[3] += (3 - 1 + 1) = 3 → arr[3] = 3
- arr[4] += (4 - 1 + 1) = 4 → arr[4] = 4
- arr[5] += (5 - 1 + 1) = 5 → arr[5] = 5
Array after 1st query:
arr = [0, 1, 2, 3, 4, 5, 0, 0, 0, 0, 0, ...]
2nd Query: l = 3, r = 8
Loop j from 3 to 8:
- arr[3] += (3 - 3 + 1) = 1 → arr[3] = 4
- arr[4] += (4 - 3 + 1) = 2 → arr[4] = 6
- arr[5] += (5 - 3 + 1) = 3 → arr[5] = 8
- arr[6] += (6 - 3 + 1) = 4 → arr[6] = 4
- arr[7] += (7 - 3 + 1) = 5 → arr[7] = 5
- arr[8] += (8 - 3 + 1) = 6 → arr[8] = 6
Array after 2nd query:
arr = [0, 1, 2, 4, 6, 8, 4, 5, 6, 0, 0, ...]
3rd Query: l = 6, r = 10
Loop j from 6 to 10:
- arr[6] += (6 - 6 + 1) = 1 → arr[6] = 5
- arr[7] += (7 - 6 + 1) = 2 → arr[7] = 7
- arr[8] += (8 - 6 + 1) = 3 → arr[8] = 9
- arr[9] += (9 - 6 + 1) = 4 → arr[9] = 4
- arr[10] += (10 - 6 + 1) = 5 → arr[10] = 5
Array after 3rd query:
arr = [0, 1, 2, 4, 6, 8, 5, 7, 9, 4, 5, 0, ...]
Querying the Results:
m = 5 (five queries for specific indices)
- Query for index 1: Output arr[1] = 1
- Query for index 4: Output arr[4] = 6
- Query for index 7: Output arr[7] = 7
- Query for index 9: Output arr[9] = 4
- Query for index 10: Output arr[10] = 5
Brute Force in all Languages
1. C++ Try on Compiler
#include <iostream>
#include <vector>
using namespace std;
// Main function
int main() {
// Read input
int n, q;
cin >> n >> q;
// Initialize vector 'ans' of size 1000002 with zeros
vector<int> ans(1000002, 0);
int l, r;
// Loop through 'q' queries
for(int i = 0; i < q; i++) {
// Read range [l, r]
cin >> l >> r;
// Increment array elements in the range [l, r]
for(int j = l; j <= r; j++) {
ans[j] += (j - l + 1);
}
}
// Read number of index queries 'm'
int m;
cin >> m;
// Process 'm' queries
while(m--) {
// Read index to query
int indx;
cin >> indx;
// Print value at that index
cout << ans[indx] << endl;
}
return 0;
}
2. Java Try on Compiler
import java.util.*;
import java.lang.*;
import java.io.*;
// Main class
class Codechef {
public static void main (String[] args) throws java.lang.Exception {
// Create Scanner object to read input
Scanner sc = new Scanner(System.in);
// Read 'n' (array size, not used) and 'q' (number of queries)
int n = sc.nextInt();
int q = sc.nextInt();
// Initialize array 'ans' with size 1000002
int ans[] = new int[1000002];
int l, r;
// Loop through 'q' queries
for(int i = 0; i < q; i++) {
// Read range [l, r]
l = sc.nextInt();
r = sc.nextInt();
// Increment array elements in the range [l, r]
for(int j = l; j <= r; j++) {
ans[j] += (j - l + 1);
}
}
// Read number of index queries 'm'
int m = sc.nextInt();
// Process 'm' queries
while(m != 0) {
// Read index to query
int indx = sc.nextInt();
// Print value at that index
System.out.println(ans[indx]);
m--;
}
}
}
3. Python Try on Compiler
# Import sys to read input faster
import sys
input = sys.stdin.read
data = input().split()
# Read 'n' and 'q'
n = int(data[0])
q = int(data[1])
# Initialize list 'ans' with size 1000002
ans = [0] * 1000002
index = 2
# Loop through 'q' queries
for _ in range(q):
# Read l and r from input
l = int(data[index])
r = int(data[index + 1])
index += 2
# Increment array elements in the range [l, r]
for j in range(l, r + 1):
ans[j] += (j - l + 1)
# Read 'm' (number of index queries)
m = int(data[index])
index += 1
# Process 'm' queries
for _ in range(m):
# Read index to query
indx = int(data[index])
index += 1
# Print value at that index
print(ans[indx])
4. JavaScript Try on Compiler
// Read input from stdin (Node.js)
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').split('\n');
// Read 'n' and 'q'
const [n, q] = input[0].split(' ').map(Number);
// Initialize array 'ans' with size 1000002
let ans = new Array(1000002).fill(0);
// Process 'q' queries
for (let i = 1; i <= q; i++) {
// Read l and r from input
let [l, r] = input[i].split(' ').map(Number);
// Increment array elements in the range [l, r]
for (let j = l; j <= r; j++) {
ans[j] += (j - l + 1);
}
}
// Read 'm' (number of index queries)
let m = parseInt(input[q + 1]);
// Process 'm' queries
for (let i = q + 2; i < q + 2 + m; i++) {
// Read index to query
let indx = parseInt(input[i]);
// Print value at that index
console.log(ans[indx]);
}
Time Complexity: O(q×n+m)
Query Processing (for-loop over q queries):
- For each query, the loop iterates over the range [l, r].
- In the worst case, this could be the entire range from 1 to n, giving a time complexity of: O(q×n)
Index Queries (while loop over m queries):
- For each of the m indices, querying is a simple lookup (O(1)).
- Total time for m queries: O(m)
Total Time Complexity: O(q×n+m)
Space Complexity: O(n)
Auxiliary Space Complexity
Auxiliary Space Complexity refers to the extra space used in the algorithm other than the input space.
Array Initialization:
An array of size 1000002 is initialized: O(1000002)≈O(10^6)= O(n)
Other Variables:
Only a few integer variables (n, q, l, r, m, indx) are used O(1)
Total Auxiliary Space: O(10^6)
Total Space Complexity (Including Input Space):
The array ans takes O(n) space.
The input data (q queries and m index queries) occupy space proportional to q + m.
The total space complexity : O(n + q + m)
Ever imagined if we had 10^6 boxes and 5 x 10^5 instructions to add candies to big sections of boxes. Walking from box to box every time would take a very long time. We have to think of a better approach rather than using the naive approach !!
Optimal Approach
Intuition
I observed that same number of candies were added between l and r. Is it necessary to visit each and every box within l and r and add 1 extra candy each time? Did you observe the same ??
Yes, This means we are saying that we are in-directly adding flags to the location l and another flag at location r stating that we can later we simply walk over the boxes once and fill in the correct number of candies.
Did the above steps remind us of something ? Yes, it's line sweep algorithm where we used to mark the two interval end-points and later sweep the values from the start to end.
And, since we sweep the values from start to end which means we carry forward the previous values. So, we are using the prefix-sum approach as well.
Let's now figure out the logical part.
When we add candies to boxes, the amount of candy added increases as we move from L to R: At box L, we add +1. At box L+1, we add +2. At box L+2, we add +3 and so on. This creates a growing pattern.
That means we will use one array to track where candies are added and one array to track the increasing pattern.
Not clear , why we used two arrays, let's understand using an example
Example Without Two Arrays
Boxes = 5 Instruction 1: Add candies from box 1 to box 3
ans[1] += 1
ans[2] += 2
ans[3] += 3
Now, when we get instruction 2: Add candies from box 2 to box 4
ans[2] += 1
ans[3] += 2
ans[4] += 3
What if n and q are large? That means for each instruction we use a lot of time.
Example With two arrays a[] and b[] (a[] for tracking and b[] for growing pattern)
Instruction 1: Add candies from box 1 to 3
a[1] += 1 → Start adding at box 1.
a[4] -= 1 → Stop adding after box 3.
b[1] += 1 → Start increasing at box 1.
b[4] -= 1 → Stop increasing after box 3.
Instruction 2: Add candies from box 2 to 4
a[2] += 1 → Start at box 2.
a[5] -= 1 → Stop after box 4.
b[2] += 1 → Start increasing at box 2.
b[5] -= 1 → Stop increasing after box 4.
When, we use two arrays
We can Start and stop adding candies in O(1) time for each instruction. We can Apply the increasing pattern smoothly by adjusting how fast the candies grow.
In other words, we use one array to track where to START and STOP adding candies.
and another array to track how much to increase as we walk.
Once, we traverse the array and we have our a[] and b[] array filled with the required values, what's next ??
We have to make use of a formula ? Let's derive it. We have an array a[] to let us know where to add candies and where to stop and b[] to track the increasing pattern.
If we want to know the total candies to be added following the instructions. It will be a[i]*(i+1).
What if there are instructions where the candies overlap?? We will use b[] , which means we will subtract b[i] from a[i]*(i+1) ?
The formula becomes:-
ans[i] = (a[i] * (i + 1)) - b[i]
Understanding the formula
- a[i]
- This tells us how many times candies were added to box i.
- It comes from the prefix sum of a[].
- a[i] = How many times this box was involved in instructions.
- (i + 1)
- This represents the box number.
- Box i is actually the (i+1)-th box (since arrays are 0-indexed in code).
- More candies go to boxes farther down the row.
- a[i] * (i + 1)
- This calculates the total candies added to box i based on how many times the box was involved (a[i]) and how far it is down the row (i+1).
- This part gives a basic estimate of how many candies are in the box.
- b[i]
- b[i] helps subtract the extra candies that were added when moving across multiple boxes.
- It comes from the prefix sum of b[].
- It adjusts for the fact that each instruction doesn’t just add candies equally – it increases step by step.
Why we subtract b[i] ?
Imagine you add candies from box 1 to box 3. Box 1 gets +1, Box 2 gets +2, Box 3 gets +3.
But when you move to box 2, it already received candies from the previous step! If we don't subtract b[i], we double-count candies.
Let's understand the use-case of both a[] and b[] along with the derived formula using an example
We have 5 boxes
Instruction 1: Add candies from box 1 to 3
Instruction 2: Add candies from box 2 to 4
After instruction 1:
a[1] += 1, a[4] -= 1
b[1] += 1, b[4] -= 1
After instruction 2:
a[2] += 1, a[5] -= 1
b[2] += 2, b[5] -= 2
Calculating ans[] = ans[i] = (a[i] * (i + 1)) - b[i]
For each box
ans[1] = (1 * 1) - 1 = 0
ans[2] = (2 * 2) - 3 = 1
ans[3] = (1 * 3) - 3 = 0
ans[4] = (0 * 4) - 1 = -1
Dry-Run
n = 15 (size of array, not used in logic)
q = 3 (number of queries)
Queries:
1 5 3 8 6 10
m = 5 (number of indices to query)
Indices to query:
1
4
7
9
10
Output:
1 6 7 4 5
Step 1: Initializing the Arrays: We initialize three arrays of size n + 1 to keep track of the updates:
- sum[]: Tracks the "increment" of each index based on the range operations.
- pre[]: Tracks the cumulative index values added in each range.
- res[]: The final results after all updates are applied.
long[] sum = new long[(int) (n + 1)]; // Size 16
long[] pre = new long[(int) (n + 1)]; // Size 16
long[] res = new long[(int) n]; // Size 15
Step 2: Processing Queries: For each query (l, r), we adjust the sum and pre arrays:
- We increment sum[l] by 1 (starting the range).
- We decrement sum[r+1] by 1 (ending the range).
- We add l to pre[l] (adding index values from l).
- We subtract l from pre[r+1] (stopping the index values after r).
Query 1: 1 5
- Increment sum[0] by 1, decrement sum[5] by 1.
- Add 0 to pre[0], subtract 0 from pre[5].
Query 2: 3 8
- Increment sum[2] by 1, decrement sum[9] by 1.
- Add 2 to pre[2], subtract 2 from pre[9].
Query 3: 6 10
- Increment sum[5] by 1, decrement sum[11] by 1.
- Add 5 to pre[5], subtract 5 from pre[11].
Step 3: Calculating Prefix Sums
After applying all updates to sum and pre, we need to calculate the prefix sums for both arrays.
sum array (after prefix sum):
sum[0] = 1
sum[1] = 1
sum[2] = 1
sum[3] = 1
sum[4] = 1
sum[5] = 2
sum[6] = 2
sum[7] = 2
sum[8] = 2
sum[9] = 1
sum[10] = 1
sum[11] = 1
sum[12] = 0
sum[13] = 0
sum[14] = 0
pre array (after prefix sum):
pre[0] = 0
pre[1] = 0
pre[2] = 2
pre[3] = 2
pre[4] = 2
pre[5] = 7
pre[6] = 7
pre[7] = 7
pre[8] = 7
pre[9] = 5
pre[10] = 5
pre[11] = 5
pre[12] = 0
pre[13] = 0
pre[14] = 0
Step 4: Calculating Results for Each Index: Now, for each index i, we compute the result using the formula:
res[i] = (sum[i] * (i + 1)) - pre[i]
For each index i, calculate the result:
- Index 0: res[0] = (1 * (0 + 1)) - 0 = 1
- Index 1: res[1] = (1 * (1 + 1)) - 0 = 2
- Index 2: res[2] = (1 * (2 + 1)) - 2 = 1
- Index 3: res[3] = (1 * (3 + 1)) - 2 = 2
- Index 4: res[4] = (1 * (4 + 1)) - 2 = 3
- Index 5: res[5] = (2 * (5 + 1)) - 7 = 6
- Index 6: res[6] = (2 * (6 + 1)) - 7 = 7
- Index 7: res[7] = (2 * (7 + 1)) - 7 = 7
- Index 8: res[8] = (2 * (8 + 1)) - 7 = 7
- Index 9: res[9] = (1 * (9 + 1)) - 5 = 5
- Index 10: res[10] = (1 * (10 + 1)) - 5 = 6
- Index 11: res[11] = (1 * (11 + 1)) - 5 = 7
- Index 12: res[12] = (0 * (12 + 1)) - 0 = 0
- Index 13: res[13] = (0 * (13 + 1)) - 0 = 0
- Index 14: res[14] = (0 * (14 + 1)) - 0 = 0
Step 5: Answering the Queries
Finally, we process the queries for indices 1, 4, 7, 9, and 10:
- Query for index 1: res[0] = 1
- Query for index 4: res[3] = 2
- Query for index 7: res[6] = 7
- Query for index 9: res[8] = 7
- Query for index 10: res[9] = 5
Final Output:
1
6
7
4
5
Optimal Code in all Languages
1. C++ Try on Compiler
#include <iostream>
#include <vector>
using namespace std;
// FastReader for efficient input handling
class Reader {
public:
// Constructor initializes input stream
Reader() {
br = new BufferedReader(new InputStreamReader(cin));
}
string next() {
// Read next token from the input
while (st == nullptr || !st.hasMoreElements()) {
try {
// Read next line and split it using StringTokenizer
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
// Return the next token from the input
return st.nextToken();
}
long nextLong() {
// Parse and return the next token as long
return st.nextLong();
}
};
int main() {
// Create Reader object for input handling
Reader input;
// Read the size of the array
long n = input.nextLong();
// Initialize sum, pre, and res arrays
vector<long> sum(n + 1, 0);
vector<long> pre(n + 1, 0);
vector<long> res(n, 0);
// Read the number of queries
long q = input.nextLong();
// Process each query
for (int i = 0; i < q; i++) {
// Read the left and right index of the query
long l = input.nextLong() - 1;
long r = input.nextLong() - 1;
// Increment the sum at left index
sum[l]++;
// Decrement the sum after the right index
sum[r + 1]--;
// Increment the pre at left index by the left value
pre[l] += l;
// Decrement the pre after the right index by the left value
pre[r + 1] -= l;
}
// Calculate prefix sums for sum and pre arrays
for (long i = 1; i < sum.size(); i++) {
// Update sum array
sum[i] += sum[i - 1];
// Update pre array
pre[i] += pre[i - 1];
}
// Calculate the result for each index
for (long i = 0; i < sum.size() - 1; i++) {
// Calculate the result using sum and pre arrays
res[i] = (sum[i] * (i + 1)) - pre[i];
}
// Read the number of indices to query
long m = input.nextLong();
// Process each query
for (long i = 0; i < m; i++) {
// Read index and output the result
long idx = input.nextLong() - 1;
cout << res[idx] << endl;
}
return 0;
}
2. Java Try on Compiler
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
// FastReader for efficient input handling
static class Reader {
BufferedReader br;
StringTokenizer st;
public Reader() {
// Create BufferedReader and StringTokenizer for efficient input handling
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
// Read next token from the input
while (st == null || !st.hasMoreElements()) {
try {
// Read next line and split it using StringTokenizer
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
// Return the next token from the input
return st.nextToken();
}
long nextLong() {
// Parse and return the next token as long
return Long.parseLong(next());
}
}
public static void main(String[] args) {
// Create Reader object for input handling
Reader input = new Reader();
// Read the size of the array
long n = input.nextLong();
// Initialize sum, pre, and res arrays
long[] sum = new long[(int) (n + 1)];
long[] pre = new long[(int) (n + 1)];
long[] res = new long[(int) n];
// Read the number of queries
long q = input.nextLong();
// Process each query
for (int i = 0; i < q; i++) {
// Read the left and right index of the query
long l = input.nextLong() - 1;
long r = input.nextLong() - 1;
// Increment the sum at left index
sum[(int) l]++;
// Decrement the sum after the right index
sum[(int) (r + 1)]--;
// Increment the pre at left index by the left value
pre[(int) l] += l;
// Decrement the pre after the right index by the left value
pre[(int) (r + 1)] -= l;
}
// Calculate prefix sums for sum and pre arrays
for (long i = 1; i < sum.length; i++) {
// Update sum array
sum[(int) i] += sum[(int) (i - 1)];
// Update pre array
pre[(int) i] += pre[(int) (i - 1)];
}
// Calculate the result for each index
for (long i = 0; i < sum.length - 1; i++) {
// Calculate the result using sum and pre arrays
res[(int) i] = (sum[(int) i] * (i + 1)) - pre[(int) i];
}
// Read the number of indices to query
long m = input.nextLong();
// Process each query
for (long i = 0; i < m; i++) {
// Read index and output the result
long idx = input.nextLong() - 1;
System.out.println(res[(int) idx]);
}
}
}
3. Python Try on Compiler
# FastReader for efficient input handling
class Reader:
def __init__(self):
# Initialize input stream
self.br = sys.stdin
self.st = None
def next(self):
# Read next token from the input
while self.st is None or not self.st:
line = self.br.readline()
self.st = line.split()
# Return the next token from the input
return self.st.pop(0)
def nextLong(self):
# Parse and return the next token as long
return int(self.next())
# Main code
input = Reader()
# Read the size of the array
n = input.nextLong()
# Initialize sum, pre, and res arrays
sum_arr = [0] * (n + 1)
pre_arr = [0] * (n + 1)
res = [0] * n
# Read the number of queries
q = input.nextLong()
# Process each query
for _ in range(q):
# Read the left and right index of the query
l = input.nextLong() - 1
r = input.nextLong() - 1
# Increment the sum at left index
sum_arr[l] += 1
# Decrement the sum after the right index
sum_arr[r + 1] -= 1
# Increment the pre at left index by the left value
pre_arr[l] += l
# Decrement the pre after the right index by the left value
pre_arr[r + 1] -= l
# Calculate prefix sums for sum and pre arrays
for i in range(1, len(sum_arr)):
sum_arr[i] += sum_arr[i - 1]
pre_arr[i] += pre_arr[i - 1]
# Calculate the result for each index
for i in range(len(sum_arr) - 1):
res[i] = (sum_arr[i] * (i + 1)) - pre_arr[i]
# Read the number of indices to query
m = input.nextLong()
# Process each query
for _ in range(m):
# Read index and output the result
idx = input.nextLong() - 1
print(res[idx])
4. JavaScript Try on Compiler
// FastReader for efficient input handling
class Reader {
constructor() {
// Initialize input stream
this.br = process.stdin;
this.st = null;
}
next() {
// Read next token from the input
while (!this.st || this.st.length === 0) {
const line = this.br.readLine();
this.st = line.split(" ");
}
// Return the next token from the input
return this.st.shift();
}
nextLong() {
// Parse and return the next token as long
return parseInt(this.next());
}
}
// Main code
const input = new Reader();
// Read the size of the array
let n = input.nextLong();
// Initialize sum, pre, and res arrays
let sum_arr = Array(n + 1).fill(0);
let pre_arr = Array(n + 1).fill(0);
let res = Array(n).fill(0);
// Read the number of queries
let q = input.nextLong();
// Process each query
for (let i = 0; i < q; i++) {
// Read the left and right index of the query
let l = input.nextLong() - 1;
let r = input.nextLong() - 1;
// Increment the sum at left index
sum_arr[l]++;
// Decrement the sum after the right index
sum_arr[r + 1]--;
// Increment the pre at left index by the left value
pre_arr[l] += l;
// Decrement the pre after the right index by the left value
pre_arr[r + 1] -= l;
}
// Calculate prefix sums for sum and pre arrays
for (let i = 1; i < sum_arr.length; i++) {
sum_arr[i] += sum_arr[i - 1];
pre_arr[i] += pre_arr[i - 1];
}
// Calculate the result for each index
for (let i = 0; i < sum_arr.length - 1; i++) {
res[i] = (sum_arr[i] * (i + 1)) - pre_arr[i];
}
// Read the number of indices to query
let m = input.nextLong();
// Process each query
for (let i = 0; i < m; i++) {
// Read index and output the result
let idx = input.nextLong() - 1;
console.log(res[idx]);
}
Time Complexity: O(n+q+m)
Query Processing Loop: For each query, we are updating values in two arrays (sum and pre) in constant time for each operation: incrementing sum[l], decrementing sum[r + 1], and adjusting the pre array. Each query processes these in O(1) time.
Prefix Sum Calculation:After processing the queries, we compute the prefix sums for the sum and pre arrays. This requires iterating through each element of the arrays once, so it is O(n) where n is the size of the array.
Final Result Calculation: We calculate the results for each index by iterating over the arrays sum and pre, which takes O(n) time.
Querying the Results: For each index query, we access an element from the res array, which is done in constant time O(1) per query. If there are m index queries, this step takes O(m) time.
Total Time Complexity O(n+q+m)
Where: n is the size of the array, q is the number of range queries, m is the number of index queries.
Space Complexity: O(n)
Auxiliary Space refers to the extra space required by an algorithm other than the input space
The algorithm uses three main arrays: sum of size n + 1 (to handle boundary conditions) , pre of size n + 1 (to handle prefix sum adjustments) , res of size n (to store the results for each index).
Hence, the auxiliary space complexity is dominated by the space used by these arrays, which is O(n).
Total Space Complexity:
Input : o(n) for the array and O(1) space for the variables.
Auxiliary space: O(n)
Therefore, the total space complexity is: O(n) + O(n) =O(2n) = O(n)
You are given a 2D integer array logs where each
logs[i] = [birth i, death i] indicates the birth and death years of the ith person.
The population of some year x is the number of people alive during that year. The ith person is counted in year x's population if x is in the inclusive range [birth i, death i- 1]. Note that the person is not counted in the year that they die.
Return the earliest year with the maximum population.
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] = [start i, end i] where start i is the starting point of the ith car and end i is the ending point of the ith car.
Return the number of integer points on the line that are covered with any part of a car.