Hey Neetcode, nice explanation! One suggestion I have is that you mention that this pattern is *Sweep Line* for viewers so they can dig into this pattern more, since its a somewhat frequent pattern for more advanced prefix sum problems. Maybe you could make some videos on the pattern since you seem to have it down (I would recommend Zero Array Transformation I & II since they're Google tagged and relatively simple to understand and visualize). Also I've put my approach to this problem is below and I think its a bit simpler to understand (excluding the character manipulation, but that can be dodged by what you did in the video by converting to integers beforehand) since it doesn't require a reverse traversal and to apply the accumulated diffs to each character in the string! Either way nice work! class Solution: def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str: # Sweep Line! # forward would insert a [+1, -1] and backward inserts a [-1, +1] for the start and end+1 positions. n = len(s) prefixes = [0] * (n + 1) # If the direction is forward, then the start is +1 and end+1 is -1, vice versa if it is backwards. for start, end, direction in shifts: prefixes[start] += 1 if direction else -1 prefixes[end + 1] -= 1 if direction else -1 for i in range(1, len(prefixes)): prefixes[i] += prefixes[i-1] # Now we just apply the shifts we've precalculated to the chars, prefixes[i] holds the offset we want to apply. res = [] for i, char in enumerate(s): new = chr(ord('a') + ((ord(char) - ord('a') + prefixes[i]) % 26)) res.append(new) return "".join(res)
Yeah that's true. Tbh i dont take notes before recording, so i just keep a list of things in my head that I want to cover, so I forget sometimes. Thanks for mentioning it though, comments like these are helpful for others so I appreciate it.
hey @soupayt I see you have a lot of experience solving problems, recognizing patterns ig so if possible can i have your social media (any) or anything through which i can contact you as i m beginner and i need some kind of guidance. Please if you could
Great solution. I spent a lot of time trying to solve it as intervals problem. However, I feel that tracking the range forward instead of backwards is more intuitive. i.e. Store shift [s,e,d] as prefix_diff[s] += d and prefix_diff[e+1] -= d
Question about 18:44 . If there are many shifts to the left, then theoretically the diff could be a very small negative number like -27, right? In that case, if we simply add 26 to it, then try to mod it in a non-Python language, wouldn't we still wind up with a negative number? Instead of simply adding 26 once, should we continuously add 26 until the sum is positive, and then do the modulus operator?
safe to say that this question and its solution deep fried my brain. Might be easy for some to understand this but it took me a long time to even understand this solution
Thank you so much for the prefix sum explanation! My first attempt involved sorting the shifts and using a min heap, and I was scratching my head wondering why it was so slow compared to all the other sample solutions.
off topic .. are you drawing by using the mouse (cos i can hear the mouse clicks) or are you using a writing tab ?? makes me wonder how difficult it would be to write on screen using the mouse
Thank you for the clear explanation. I read the editorial solution on Leetcode but found it challenging to grasp the intuition behind the prefix approach. How do you develop insight into this two-prefix method? I tried debugging and printing variables like the difference or prefix array, but it didn’t help much. Do you have any tips for understanding such approaches better?
Question: is there any reason that you have to traverse right to left? Could you traverse the diff array from the other direction? If you change your mapping scheme -> L=1 & R=-1 (forward) and L=-1 & R=1 (backwards)?
Great video, Neet! You explained this problem very well-definitely a little tricky one. I was wondering, doesn't this prefix approach have a time complexity of O(n + m)? 13:28
Hey Neet. Thank you for the video. I think that adding 26 to make modulo work in previous languages should happen sooner (when you are making the prefix array). In theory the line "diff + res[i-1] + 26" could still be negative and it would not work in other languages.
Ok but whats the point in complicating it with running it in reverse and having offset positions? I did a similar solution but just set start to +1 and end+1 to -1 (in the case of forward shift). Then they will be mapped directly onto eachother and you can iterate forwards code, 3ms beats 81%, memory beats 78%. If anybody knows how to make it better please tell me. except making the vector +1 length so I dont need to make the if else statement in the first loop. class Solution { public: string shiftingLetters(string s, vector& shifts) { std::vector moves(s.length(), 0); for(const auto &shift: shifts){ if(shift[2]){ moves[shift[0]]++; if(shift[1]+1 < moves.size()) moves[shift[1]+1]--;
Can someone please explain what is the intuition behind using prefix array + diff in this question? And , How to approach this types of problem in an interview?
I wonder what mystery quirk led to this "reverse" solution. My solution is mostly the same, but I add to prefix if direction is 1 and I iterate from 0 to n.
Beginners should focus on coming up with their own code first, it may not be so clean. but after that we can make it concise with the neetcode's explanation and learn how he optimised it. This way the learning can happen and we can apply the knowledge next time. I came up with following code: class Solution: def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str: prefix = [0] * (len(s) + 1) for start, end, direction in shifts: direction = -1 if direction == 0 else 1 prefix[start] += direction prefix[end + 1] += (-1 * direction)
ans = [] #use prefix and find the ans diff = 0 for i in range(len(s)): diff += prefix[i] newCh = chr(ord('a') + (((ord(s[i]) + diff) - ord('a') + 26)%26)) ans.append(newCh) return "".join(ans)
in python in order to handle negative shifts you don't need to add 26 and then mod the result by 26 as you did. your case example: ( - 1 + 26 ) % 26 = 25 % 26 = 25 how you could have done: -1 % 26 = 25 yes, python handles negative values on mod operations gracefully
Honestly, I almost didn't understand this solution, maybe I need to look at it a couple more times and then it will become easier. But it looks very complicated.
What a shitty problem (if you have to solve it in O(n)) to get in interview to determine if the candidate is good engineer goddam though great explanation as usual!! If it will help for someone here is simple and EASY brute force solution in kotlin: fun shiftingLetters(s: String, shifts: Array): String { val asciiValues = IntArray(s.length) for(i in s.indices){ asciiValues[i] = s[i].code // init with the input s string the ascii values } for(shift in shifts){ for(index in shift[0]..shift[1]){ if(shift[2] == 1){ asciiValues[index]+=1 if(asciiValues[index] > 'z'.code){ asciiValues[index] = 'a'.code } } else { asciiValues[index]-=1 if(asciiValues[index] < 'a'.code){ asciiValues[index] = 'z'.code } } } } return asciiValues.map { it.toChar() }.joinToString("") }
class Solution: def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str: cum = [0] * (len(s) + 1) for i, j, d in shifts: if d == 0: d = -1 cum[i] += d cum[j + 1]-= d cur = 0 ans = "" for i in range(len(s)): cur += cum[i] ans += chr(97 + (ord(s[i]) - 97 + cur) % 26) return ans
Who else coming here from the daily question after time limit exceeded?
haha yes, me too
Mee😅
32/39
@@ajitpalsingh606 me
I pretty much know brute force gives tle I came directly
Never in a million years i could have a thought process like this damn
Hey Neetcode, nice explanation! One suggestion I have is that you mention that this pattern is *Sweep Line* for viewers so they can dig into this pattern more, since its a somewhat frequent pattern for more advanced prefix sum problems. Maybe you could make some videos on the pattern since you seem to have it down (I would recommend Zero Array Transformation I & II since they're Google tagged and relatively simple to understand and visualize).
Also I've put my approach to this problem is below and I think its a bit simpler to understand (excluding the character manipulation, but that can be dodged by what you did in the video by converting to integers beforehand) since it doesn't require a reverse traversal and to apply the accumulated diffs to each character in the string! Either way nice work!
class Solution:
def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
# Sweep Line!
# forward would insert a [+1, -1] and backward inserts a [-1, +1] for the start and end+1 positions.
n = len(s)
prefixes = [0] * (n + 1)
# If the direction is forward, then the start is +1 and end+1 is -1, vice versa if it is backwards.
for start, end, direction in shifts:
prefixes[start] += 1 if direction else -1
prefixes[end + 1] -= 1 if direction else -1
for i in range(1, len(prefixes)):
prefixes[i] += prefixes[i-1]
# Now we just apply the shifts we've precalculated to the chars, prefixes[i] holds the offset we want to apply.
res = []
for i, char in enumerate(s):
new = chr(ord('a') + ((ord(char) - ord('a') + prefixes[i]) % 26))
res.append(new)
return "".join(res)
Yeah that's true. Tbh i dont take notes before recording, so i just keep a list of things in my head that I want to cover, so I forget sometimes.
Thanks for mentioning it though, comments like these are helpful for others so I appreciate it.
hey @soupayt I see you have a lot of experience solving problems, recognizing patterns ig so if possible can i have your social media (any) or anything through which i can contact you as i m beginner and i need some kind of guidance. Please if you could
watched all the videos related to this question ... literally no body made me understand better than you did
i was stumped after my first approach got TLE
Haha same! I even went back to solve Shifting Letters 1 and did it in 5 minutes and was still stuck here
same here
32/39😢
Great solution. I spent a lot of time trying to solve it as intervals problem. However, I feel that tracking the range forward instead of backwards is more intuitive. i.e. Store shift [s,e,d] as prefix_diff[s] += d and prefix_diff[e+1] -= d
This is such an insane solution. It looked complicated at first. But it's really simple after you did the dry run
Question about 18:44 . If there are many shifts to the left, then theoretically the diff could be a very small negative number like -27, right? In that case, if we simply add 26 to it, then try to mod it in a non-Python language, wouldn't we still wind up with a negative number? Instead of simply adding 26 once, should we continuously add 26 until the sum is positive, and then do the modulus operator?
Love youuu Neeet ❤
love you too
@@NeetCodeIO made my day!
safe to say that this question and its solution deep fried my brain. Might be easy for some to understand this but it took me a long time to even understand this solution
the prefix trick of today, amazing. I knew Prefix would help but just couldn't figure out how.
Thank you as usual Neet for all of these!
18:58 special number in Runtime Beats
😋
Thank you so much for the prefix sum explanation! My first attempt involved sorting the shifts and using a min heap, and I was scratching my head wondering why it was so slow compared to all the other sample solutions.
The way you explained Difference Array technique is awesome.
Here's something cool i learnt in python
-1%26=25
Never expected this to work, makes it a lot easier
please add the thought process like you have done in this video,, it helps me to recheck whether i have thought the same or not
Why is the prefix array length s+1 in the example if index 0 is never used?
off topic .. are you drawing by using the mouse (cos i can hear the mouse clicks) or are you using a writing tab ?? makes me wonder how difficult it would be to write on screen using the mouse
The TLE solution was pretty easy to come by, but this one was very difficult not gonna lie
why did you put -1 for 1 on 12:19
Thank you for the clear explanation. I read the editorial solution on Leetcode but found it challenging to grasp the intuition behind the prefix approach. How do you develop insight into this two-prefix method? I tried debugging and printing variables like the difference or prefix array, but it didn’t help much. Do you have any tips for understanding such approaches better?
Question: is there any reason that you have to traverse right to left? Could you traverse the diff array from the other direction? If you change your mapping scheme -> L=1 & R=-1 (forward) and L=-1 & R=1 (backwards)?
brilliant as always
Great video, Neet! You explained this problem very well-definitely a little tricky one.
I was wondering, doesn't this prefix approach have a time complexity of O(n + m)? 13:28
Hey Neet. Thank you for the video. I think that adding 26 to make modulo work in previous languages should happen sooner (when you are making the prefix array). In theory the line "diff + res[i-1] + 26" could still be negative and it would not work in other languages.
In other languages you would just need to mod the diff by 26 since it could be huge.
Thanku so much for today's solution
9:20 mind blown.
thanks for visual explaination, i was stuck after simulation approach, now learn one more pattern
Ok but whats the point in complicating it with running it in reverse and having offset positions?
I did a similar solution but just set start to +1 and end+1 to -1 (in the case of forward shift). Then they will be mapped directly onto eachother and you can iterate forwards
code, 3ms beats 81%, memory beats 78%. If anybody knows how to make it better please tell me. except making the vector +1 length so I dont need to make the if else statement in the first loop.
class Solution {
public:
string shiftingLetters(string s, vector& shifts) {
std::vector moves(s.length(), 0);
for(const auto &shift: shifts){
if(shift[2]){
moves[shift[0]]++;
if(shift[1]+1 < moves.size()) moves[shift[1]+1]--;
}else{
moves[shift[0]]--;
if(shift[1]+1 < moves.size()) moves[shift[1]+1]++;
}
}
int move = 0;
for(int i = 0; i < moves.size(); i++){
move += moves[i];
move = (move + 26) % 26;
s[i] = 'a' + (s[i] - 'a' + move+26) % 26;
}
return s;
}
};
fixed the vector length and it runs 0ms
This question should be categorized as "Hard". I bet a few people can come up with this solution without any clues
Can someone please explain what is the intuition behind using prefix array + diff in this question? And , How to approach this types of problem in an interview?
I had to do something like while(diff
char shiftChar(char c, int i) {
int shift = (c - 'a' + i) % 26;
if (shift < 0) shift += 26;
char ans = 'a' + shift;
return ans;
} T_T
@@raghavkaul-nm4be it's always better to add full code instead of partial code with badly named variables
Can you make a detailed video on Sweep Line?
Hey man could you please do a video about segment tree? Like you can solve a lc problem and teach us while you solving. Thanks
I wonder what mystery quirk led to this "reverse" solution. My solution is mostly the same, but I add to prefix if direction is 1 and I iterate from 0 to n.
I paused the video to go and solve Shifting Letters 1 before coming back lol.
Another algorithm I didn't know, add it to the list
In the second example, the update was made at index 3, but the left was at index 2 ???
you are a genius, thank you, it help me a lot
Beginners should focus on coming up with their own code first, it may not be so clean. but after that we can make it concise with the neetcode's explanation and learn how he optimised it. This way the learning can happen and we can apply the knowledge next time.
I came up with following code:
class Solution:
def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
prefix = [0] * (len(s) + 1)
for start, end, direction in shifts:
direction = -1 if direction == 0 else 1
prefix[start] += direction
prefix[end + 1] += (-1 * direction)
ans = []
#use prefix and find the ans
diff = 0
for i in range(len(s)):
diff += prefix[i]
newCh = chr(ord('a') + (((ord(s[i]) + diff) - ord('a') + 26)%26))
ans.append(newCh)
return "".join(ans)
Vamos!
is this a common technique or something?
cuz i've never seen it and i could never come up with it
that's freaking genius
in python in order to handle negative shifts you don't need to add 26 and then mod the result by 26 as you did.
your case example:
( - 1 + 26 ) % 26 = 25 % 26 = 25
how you could have done:
-1 % 26 = 25
yes, python handles negative values on mod operations gracefully
Didn't I mention that? I ran the code in the video without the +26 and it also worked.
Beats 69.69% very nice 👌
video starts at 6:44
Honestly, I almost didn't understand this solution, maybe I need to look at it a couple more times and then it will become easier. But it looks very complicated.
Can't we just map the letters in a hash map and do the operations easily
Solved it just now
TLE 🧘🏼
GOAT GOAT GOAT
-1%26 also = 25.. :/
What a shitty problem (if you have to solve it in O(n)) to get in interview to determine if the candidate is good engineer goddam though great explanation as usual!!
If it will help for someone here is simple and EASY brute force solution in kotlin:
fun shiftingLetters(s: String, shifts: Array): String {
val asciiValues = IntArray(s.length)
for(i in s.indices){
asciiValues[i] = s[i].code // init with the input s string the ascii values
}
for(shift in shifts){
for(index in shift[0]..shift[1]){
if(shift[2] == 1){
asciiValues[index]+=1
if(asciiValues[index] > 'z'.code){
asciiValues[index] = 'a'.code
}
}
else {
asciiValues[index]-=1
if(asciiValues[index] < 'a'.code){
asciiValues[index] = 'z'.code
}
}
}
}
return asciiValues.map { it.toChar() }.joinToString("")
}
class Solution:
def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
cum = [0] * (len(s) + 1)
for i, j, d in shifts:
if d == 0:
d = -1
cum[i] += d
cum[j + 1]-= d
cur = 0
ans = ""
for i in range(len(s)):
cur += cum[i]
ans += chr(97 + (ord(s[i]) - 97 + cur) % 26)
return ans
Lol wouldn't even remotely think of this solution. I'm gonna take my TLE as a dub 🥲