Nice explanation. I did not understand subtracting the value from (end_index + 1). Would be helpful if you can explain that part. Looking for more videos. Thanks
Sure. So we are looking for the max value performed after the queries are done. The subtraction of the value at end_index + 1 represents the first value that the current queries value was not added to. This allows us to simply add up all the values in the array, and have the correct value at every given index at the end. So, if my query was 1 2 1 that would create the array 1 1 0, but to make that process faster for the sake of finding the max, I can represent the same information as 1 0 -1 where each index value is the sum up to that index. Does that make sense?
For all people wondering why this works, the data is represented in a way that any index's value is actually the sum of all the values behind it. So finally we just add them up.
"Why we add -k to 1st element outside of the region": To better understand/feel the solution - let's make a manageable - small example with only one element in 2 not overlapping regions: For simplicity let's use 0 base index: a b k 0 0 200 1 1 300 0 1 200 300 Result must be 300. After 1st cycle we would have: 0: 200 1: -200 -200 is a accumulated "penalty" of not being in the region After 2nd: 0:200 1: -200+300 => 0:200 1:100 You can immediately see that the final result: 200 + 100 = 300 Number at each index is the sum of all overlapped regions k values and penalties of not overlapped ones. Hope it makes sense.
Yes the important point is that each index's actual value is the sum of all the preceding values, that's why we have to do the decreasing of value at the k+1th index.
You got the complexity part wrong though. Running time of the direct approach is O(q*n) because as you iterate over the queries, you are updating a part of the array with a value, and since each time the index range to modify changes we take it as the array size n itself since that is the maximum range we can be given. And then finally, iterating over array to find maximum will be linear time. So overall complexity is kind of like O(N^2); In your simpler approach it will take only linear time or to be specific O(q) time where q is number of queries, which is likely to be larger than the array itself. So this approach will run in O(N) time.
This algorithm is already crazy fast, so we could not process faster in terms of big O. However, if we knew we were dealing with insanely large data set we could get O/n on average by threading n threads. The only issue that could arise with multiple threads is if both are calling += operator at the same time and read from the registry a non-upadated value then the written value would be wrong for that index. So, there would have to be some kind of added thread management which in most cases would not contribute to a meaningful difference in perf. Good question though.
Hi @Brian, I am getting indexoutofbound of exception, could you please help me with this arrayManipulation(int n, List queries) { List temp = new ArrayList(n);
for(List query:queries) { int startIndex=query.get(0)-1; int endIndex=query.get(1)-1; int val=query.get(2); temp.set(startIndex,temp.get(startIndex)+val); if(endIndex+1max){ max=curVal; } }
I impemented this logic in java...but the third test case isn't passing...Can you help me please? Code :- public static long arrayManipulation(int n, List queries) { long arr[] = new long[n]; long max=Long.MIN_VALUE; long cur=0;
Okay, your error is on the subtraction. To make the code more human readable I broke everything out into what it was expressing. However, for your more condensed version of the code you do not do the -1 on the subtraction side, as the 1 based indexed array will already have the end index + 1 built in which is where you are wanting to subtract. However, since this will result in an out of bounds index when the value is greater than the size of the array you need to wrap it in a check: if(listy.get(1) < n) { arr[listy.get(1) -= listy.get(2); } in the place of arr[listy.get(1) - 1] -= listy.get(2);
I'm just beginning my programming journey, so I'm curious how do you come up with this solution? Have you seen this solution in the past and you just re-used it or do you have a way of just coming up with a solution on the fly?
Um… a little bit of both I suppose. Programming is just problem solving with code; after solving a lot of problems you start to be able to break more complicated problems into either compounds of simpler problems, or variations of similar problems which allows you to start thinking algorithmically. Which just means solving the problem in a defined, repeatable steps.. I think people tend to start thinking towards these concepts after awhile, but I also went to school for CS and took algorithms which also gives me a good amount of information to draw from.. so I think it’s a mixture of past experience and intuition, if that make sense?
Hmm interesting twist on the problem, let's think about that. So, let's assume that the array length is 10; the literal representation of that query would be 4 4 4 0 0 0 0 4 4 4. If we were to try our trick we would get 0 0 0 -4 0 0 0 0 4 0 0 which would not work, as every value is off by exactly 4. The trick in this case would be to have a check if the second value is greater than the first, if so we have a wrap around in which case we do the same thing as before, but we add k to the first index as well. For your example it would be represented as 4 0 0 -4 0 0 0 0 4 0 0. Does that make sense?
So the whole thing here seems to be data representation. Like, every index value is inferred as the sum of all the values behind it, so we don't have make a literal modification to every index value.
Really not a fan of HackerRank... mouthful, unspecific, and ambiguous description with a weird input format. I'd say 80% the difficulty came from reading the description. Have to practice it as I got online test assessment using this platform from the company I applied. Duh...
Hi @Brian, I convert List to arrays, then five cases are success others are failed due to runtime public static long arrayManipulation(int n, List queries) { // Write your code here long max=Integer.MIN_VALUE; int curVal=0; int []temp=new int[n]; for(int i=0;i
really appreciate your effort. Your explaination is much better than hacker rank description.
Well it's only a description, it just explains the problem not it's solution.
thanks you're the only one that managed to make me understand this after only 6 min of watching your video, great job !!
Glad to help!
you're ability to break down the problem is outstanding, my problem is thinking it in simple terms...hope i get there soon.. Thanks man!!
Thank you I appreciate it. I Know you'll get there one day as well.
Thank you for the hard work, this explanation is so much better than other videos that I can find.
Words cannot express how amazing this video was. If every coding video was like yours, Mars would be colonized already.
Haha thanks for the kind words, although I am unsure of their accuracy 🤣
Very nice, it's like a new way of thinking about and representing data.
Nice explanation. I did not understand subtracting the value from (end_index + 1). Would be helpful if you can explain that part. Looking for more videos. Thanks
Sure. So we are looking for the max value performed after the queries are done. The subtraction of the value at end_index + 1 represents the first value that the current queries value was not added to. This allows us to simply add up all the values in the array, and have the correct value at every given index at the end. So, if my query was 1 2 1 that would create the array 1 1 0, but to make that process faster for the sake of finding the max, I can represent the same information as 1 0 -1 where each index value is the sum up to that index. Does that make sense?
@@briandyck8828 Yes, thank you.
@@sudheendrasampath No problem! Glad to help!
Thanks Brian for this video, definitively helps a lot!
Glad to help!
For all people wondering why this works, the data is represented in a way that any index's value is actually the sum of all the values behind it. So finally we just add them up.
Excellent thanks Brian
Great explanation! Thanks
Thank you so much for this explanation
No problem! Glad to help!
Lovely ♥
I am glad you enjoyed it! More content soon!
Crack, after your explanation in my first attempt I could solve it, thanks for help me to do it.
"Why we add -k to 1st element outside of the region":
To better understand/feel the solution - let's make a manageable - small example with only one element in 2 not overlapping regions:
For simplicity let's use 0 base index:
a b k
0 0 200
1 1 300
0 1
200
300
Result must be 300.
After 1st cycle we would have:
0: 200 1: -200
-200 is a accumulated "penalty" of not being in the region
After 2nd:
0:200 1: -200+300 => 0:200 1:100
You can immediately see that the final result: 200 + 100 = 300
Number at each index is the sum of all overlapped regions k values and penalties of not overlapped ones. Hope it makes sense.
Yes the important point is that each index's actual value is the sum of all the preceding values, that's why we have to do the decreasing of value at the k+1th index.
But to arrive at this kind of a solution is what is great.
You got the complexity part wrong though. Running time of the direct approach is O(q*n) because as you iterate over the queries, you are updating a part of the array with a value, and since each time the index range to modify changes we take it as the array size n itself since that is the maximum range we can be given.
And then finally, iterating over array to find maximum will be linear time. So overall complexity is kind of like O(N^2);
In your simpler approach it will take only linear time or to be specific O(q) time where q is number of queries, which is likely to be larger than the array itself. So this approach will run in O(N) time.
You are right, I said m * n then said just shy of cubed when I meant squared. Good catch
Thank you so much
really nice video, well done and well explained. question: which is the math subject that explain the solution that you find?
I believe it is just Arithmetic, with Discrete Math logic.
could you please make a video for tips on how to breakdown a problem
I will see if I can think of a way to articulate it.
I was wondering if we could thread the algorithm to process the queries faster.
This algorithm is already crazy fast, so we could not process faster in terms of big O. However, if we knew we were dealing with insanely large data set we could get O/n on average by threading n threads. The only issue that could arise with multiple threads is if both are calling += operator at the same time and read from the registry a non-upadated value then the written value would be wrong for that index. So, there would have to be some kind of added thread management which in most cases would not contribute to a meaningful difference in perf. Good question though.
Hi @Brian, I am getting indexoutofbound of exception, could you please help me with this
arrayManipulation(int n, List queries) {
List temp = new ArrayList(n);
for(List query:queries) {
int startIndex=query.get(0)-1;
int endIndex=query.get(1)-1;
int val=query.get(2);
temp.set(startIndex,temp.get(startIndex)+val);
if(endIndex+1max){
max=curVal;
}
}
I impemented this logic in java...but the third test case isn't passing...Can you help me please?
Code :-
public static long arrayManipulation(int n, List queries) {
long arr[] = new long[n]; long max=Long.MIN_VALUE;
long cur=0;
for(List listy : queries)
{
arr[listy.get(0)-1]+= listy.get(2);
arr[listy.get(1)-1 ]-= listy.get(2);
}
for(int i=0;imax) max=cur;
}
return max;
}
}
I'll take a look at it tonight
@@briandyck8828 Thanku so much 😊
@@ashisenchoudhury162 Sorry, I got home later than expected yesterday and crashed I will look at it now.
Okay, your error is on the subtraction. To make the code more human readable I broke everything out into what it was expressing. However, for your more condensed version of the code you do not do the -1 on the subtraction side, as the 1 based indexed array will already have the end index + 1 built in which is where you are wanting to subtract. However, since this will result in an out of bounds index when the value is greater than the size of the array you need to wrap it in a check:
if(listy.get(1) < n)
{
arr[listy.get(1) -= listy.get(2);
}
in the place of arr[listy.get(1) - 1] -= listy.get(2);
@@briandyck8828 Okay I get it now...Thank you so much for helping... really grateful for your patience!
I'm just beginning my programming journey, so I'm curious how do you come up with this solution? Have you seen this solution in the past and you just re-used it or do you have a way of just coming up with a solution on the fly?
Um… a little bit of both I suppose. Programming is just problem solving with code; after solving a lot of problems you start to be able to break more complicated problems into either compounds of simpler problems, or variations of similar problems which allows you to start thinking algorithmically. Which just means solving the problem in a defined, repeatable steps.. I think people tend to start thinking towards these concepts after awhile, but I also went to school for CS and took algorithms which also gives me a good amount of information to draw from.. so I think it’s a mixture of past experience and intuition, if that make sense?
Follow up: what if it's a cyclic array and the queries can be like '8 3 4'.
Hmm interesting twist on the problem, let's think about that. So, let's assume that the array length is 10; the literal representation of that query would be 4 4 4 0 0 0 0 4 4 4. If we were to try our trick we would get 0 0 0 -4 0 0 0 0 4 0 0 which would not work, as every value is off by exactly 4. The trick in this case would be to have a check if the second value is greater than the first, if so we have a wrap around in which case we do the same thing as before, but we add k to the first index as well. For your example it would be represented as 4 0 0 -4 0 0 0 0 4 0 0. Does that make sense?
@@briandyck8828 yes makes sense.
So the whole thing here seems to be data representation. Like, every index value is inferred as the sum of all the values behind it, so we don't have make a literal modification to every index value.
hard to understand the questions itself. Can someone explain in simple words.
didnt understand the logic of adding -3 at 6 th index and remaining indices be all zero 2-4..can you explain pls in detail
Really not a fan of HackerRank... mouthful, unspecific, and ambiguous description with a weird input format. I'd say 80% the difficulty came from reading the description. Have to practice it as I got online test assessment using this platform from the company I applied. Duh...
Hi @Brian, I convert List to arrays, then five cases are success others are failed due to runtime
public static long arrayManipulation(int n, List queries) {
// Write your code here
long max=Integer.MIN_VALUE;
int curVal=0;
int []temp=new int[n];
for(int i=0;i