Shifting Letters II | Leetcode 2381 | Difference Array Technique: Concepts & Questions - 2 | MIK

Hi Everyone, this is the 2nd video of our Playlist "Difference Array Technique : Concepts & Questions".
We have already studied powerful Difference Array technique -
Now we will be solving a very good problem based on it - Shifting Letters II | Leetcode 2381 | Difference Array Technique: Concepts & Questions - 2 | codestorywithMIK

Problem Name : Shifting Letters II | Leetcode 2381 | Difference Array Technique: Concepts & Questions - 2 | codestorywithMIK
Company Tags : Will update later

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Video Summary :
This solution efficiently handles multiple range-based character shifts on a string using a difference array technique:
Difference Array Construction:
A diff array is initialized to record the net effect of all shifts at each position.
For each range [start, end] in shifts:
If the shift direction is forward (1), increment diff[start] and decrement diff[end + 1] (if within bounds).
If the direction is backward (0), decrement diff[start] and increment diff[end + 1] (if within bounds).

Prefix Sum Calculation:
The diff array is converted into a cumulative prefix sum, which gives the net shift effect for each character in the string.

Apply Shifts to the String:
For each character in the string:
Calculate the effective shift by taking diff[i] % 26 (to handle wrap-around within the alphabet).
Adjust negative shifts to positive by adding 26.
Apply the shift to the character using modular arithmetic to ensure the result stays within valid alphabetic bounds.

✨ Timelines✨
00:00 - Introduction
0:21 - Motivation
0:44 - Problem Explanation
5:22 - Thought Process and why Difference Array Technique
14:55 - Example Dry Run
19:50 - Important Part - How to apply shifts
25:41 - Corner Case
30:18 - Coding it up

#MIK #mik #Mik
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[codewith_me]

Thank you sir jo aapne isse pehle wali video upload ki thi usi concept se mene ye problem solve kr li

[bhuppidhamii]

Choti se choti chiz, aapne itne aache se samzaya h, bhaiya.

Lots of love 💗

[SudhanshuSingh-jnlw]

Thanks a lot. Difference array technique is crystal clear now.

[CODEWITHEASE-ul]

bas aaj ke baad kabhi difference array technique wali problems mei TLE nahi khaunga thank you so much🙏

[Ankitkumar-fzkc]

Thanks, I already have solved the problem. Just came here to keep up my consistent and learn something new.

[aryansinha]

Sometimes after so much effort put into thinking how to solve the potd, and then watching your solution feels like, thank you God for his(your) existence. Really man thank you. btw motivation in the beginning, something which was very much needed. Love and respect always.

[ToonDubberDuo]

thank you, i could code it watching your intuition from the other video and taking ideas from other's code

[anuragprajapati]

Bhaiya apka channel bahut underrated hai, your channel deserves millions subscribers❤❤

[sourabhsinghbhadouriya]

Sir weekly aur bi-weekly contest ke solutions bhi bna diya karo ❤

[nikhilsoni]

bhaiyya you are having long videos but are worth watching🤟💯

[nikhilsoni]

bhaiya, i was searching for your video since morning to solve POTD !!

[gui-codes]

I solved Leetcode-370 also and this problem also after watching the first video of this playlist. I never knew about Difference Array Technique, all thanks to you LEGEND MIK

[time_squarre]

Sloved this question using brute force approach and 37/39 testcases passed.

[vishwashsoni]

sir this is how solved today's POTD question after watching your intuition video :

class Solution {
public:
string shiftingLetters(string s, vector<vector<int>>& shifts) {
int n = s.size();
vector<int>vec(n, 0);
for(auto& shift : shifts){
int left = shift[0];
int right = shift[1];
int x = shift[2];

if(x == 1){
vec[left] += 1;
if(right + 1 < n){
vec[right+1] += -1;
}
}
else{
vec[left] += -1;
if(right + 1 < n){
vec[right+1] += 1;
}
}
}
for(int i=1;i<n;i++){
vec[i] += vec[i-1];
}

for(int i=0;i<n;i++){
int noOfFlips = vec[i] % 26;

if(noOfFlips < 0){
noOfFlips += 26;
}

s[i] = ((s[i] - 'a' + noOfFlips) % 26) + 'a';
}
return s;
}
};
😁

[AmandeepSingh-uqwp]

Sharing code of Shifting Letter I and II (If someone wants to see) :
Shifting Letters | :
class Solution {
public:
string shiftingLetters(string s, vector<int>& shifts) {
int n = s.size();
vector<long long> rangeUpdates(n + 1, 0);
int q = shifts.size();

for (int i = 0; i < q; i++) {
int start = 0;
int end = i;
int value = shifts[i];

rangeUpdates[start] += value;
if (end + 1 < n) {
rangeUpdates[end + 1] -= value;
}
}

long long sum = 0;
for (int i = 0; i < n; i++) {
sum += rangeUpdates[i];
sum = (sum % 26 + 26) % 26;
s[i] = (s[i] - 'a' + sum) % 26 + 'a';
}

return s;
}
};


Shifting Letters || :
class Solution {
public:
string shiftingLetters(string s, vector<vector<int>>& shifts) {
int n = s.size();
vector<long long> rangeUpdates(n + 1, 0);
int q = shifts.size();

for (int i = 0; i < q; i++) {
int start = shifts[i][0];
int end = shifts[i][1];
int direction = shifts[i][2];

rangeUpdates[start] += (direction == 1 ? 1 : -1);
if (end + 1 < n) {
rangeUpdates[end + 1] -= (direction == 1 ? 1 : -1);
}
}

long long sum = 0;
for (int i = 0; i < n; i++) {
sum += rangeUpdates[i];
sum = (sum % 26 + 26) % 26;
s[i] = (s[i] - 'a' + sum) % 26 + 'a';
}

return s;
}
};

[amanjaiswal]

Please a video on line sweep technique

[indianengineer]

6:20 indirectly kar toh hum update hee rhe hain na string ki value ko usko backward and forward move karke ?

[aadityaraj]

1943 que leetcode, is exactly difference array techinque question 😊

[OtakRajCodes]

Here is the similar java code :
class Solution {
public String shiftingLetters(String s, int[][] shifts) {
int n = s.length();
int diff[] = new int[n];

for(int shift[] : shifts){
int left = shift[0];
int right = shift[1];
int x = shift[2] == 1 ? 1 : -1;

diff[left] += x;

if(right+1 < n){
diff[right+1] -= x;
}
}

// find cumilative sum
for(int i=1;i<n;i++){
diff[i] += diff[i-1];
}

// shift chars
String newStr = "";
for(int i=0;i<n;i++){
int shift = diff[i]%26;
if(shift<0){
shift += 26;
}

char ch = (char)((((s.charAt(i) - 'a') + shift) % 26) + 'a');
newStr += ch;
}

return newStr;
}
}

[abhayshukla]

bhaiya please cover concept like rolling hash