📚 Table of Contents

1. Introduction

2. Problem 1: Two Sum

3. Problem 2: Valid Sudoku

4. Problem 3: Rotate Image

5. Problem 4: Reverse String

6. Conclusion

📝 Introduction

Today marks another step forward in my 90 Days DSA Challenge curated by Anuj Kumar. As part of this journey, I focused on solving four classic and widely-asked DSA problems: Two Sum, Valid Sudoku, Rotate Image, and Reverse String. Each of these problems tested different aspects of problem-solving — from array manipulation to matrix transformations and string handling. In this blog post, I’ll walk you through my approach, thought process, and the Java code I used to solve each problem. Whether you're following the same DSA sheet or just looking to brush up on your skills, I hope this breakdown helps clarify these concepts for you.

Let’s dive right into the solutions! 🚀

🧩 Problem 1: Two Sum

📖 Problem:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //**********Method 1******************* */
         Map<Integer,Integer>map=new HashMap<>();
         for(int i=0;i<nums.length;i++){
             map.put(nums[i],i);
         }
         for(int i=0;i<nums.length;i++){
             int lookupnum=target-nums[i];
            if(map.containsKey(lookupnum) && map.get(lookupnum)!=i){
              return new int[]{
                  map.get(lookupnum),
                   i
               };
           }
         }

💭 Approach (Using HashMap – Method 1):

To solve this efficiently in linear time, we use a HashMap to store the value-to-index mapping of elements in the array. The idea is simple:

1. First, fill the map with all array elements and their indices.

2. Then, loop through the array again, and for each element:

   • Compute its complement → target - nums[i]

   • Check if this complement exists in the map and is not the same index (to avoid using the same element twice).

   • If yes, return both indices.

   • 🔍 Code Walkthrough (Java):

       Map<Integer, Integer> map = new HashMap<>();
     

     🛠️ We create a map to store values along with their index.

       for (int i = 0; i < nums.length; i++) {
           map.put(nums[i], i);
       }
     

     📦 First, we store every value with its position in the list.

       for (int i = 0; i < nums.length; i++) {
           int lookupnum = target - nums[i];
     

     💡 Now for each item, we calculate what price we still need (the complement) to make the sum = target.

       if (map.containsKey(lookupnum) && map.get(lookupnum) != i) {
     

     🔍 Check if the complement exists in the map and is not the same item.

       return new int[] { map.get(lookupnum), i };
     

     🎯 If it exists, return the index of complement and the current item index.

🔧 Method 2: Single Pass with HashMap

Map<Integer, Integer> map = new HashMap<>();

• We use a HashMap to store each number and its index.

• Key = nums[i], Value = i

for (int i = 0; i < nums.length; i++) {
    int lookupnum = target - nums[i];

• For every number nums[i], we calculate the value lookupnum that would complete the pair:

  lookupnum=target−nums[i]\text{lookupnum} = \text{target} - \text{nums[i]}lookupnum=target−nums[i]

if (map.containsKey(lookupnum)) {
        return new int[] { map.get(lookupnum), i };
    }

• We check if lookupnum already exists in the map.

  • If it exists → we have found the two indices:
    map.get(lookupnum) (previous index) and i (current index)

map.put(nums[i], i);
}

• If no match is found yet, we store the current element in the map so it can be checked later as a possible pair.

return new int[] { -1, -1 };

• This is a fallback in case no solution is found.
  (Won’t happen in valid test cases)

---

📘 Dry Run Example

Let’s run on:

nums = [2, 11, 7, 15], target = 9

Step-by-step Execution:

✔️ Output: [0, 2]

🧩 Problem 2:Valid Sudoku

Problem:

Code:

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int [][]rows=new int[9][9];
        int [][]cols=new int[9][9];
        int [][]boxes=new int[9][9];
        for(int r=0;r<9;r=r+1){
            for(int c=0;c<9;c=c+1){
                if(board[r][c] == '.'){
                    continue;
                }


                int val=board[r][c] - '1'; 
                if(rows[r][val]==1{
                    return false;
                }
                rows[r][val]=1;
                if(cols[c][val]==1){
                    return false;
                }
                cols[c][val]=1;
                int boxidx=3*(r/3)+(c/3);  
                if(boxes[boxidx][val]==1){
                    return false;
                }
                boxes[boxidx][val]=1;
            }
        }
        return true;
    }
}

💡 Code Explanation (Line by Line)

int [][]rows = new int[9][9];
int [][]cols = new int[9][9];
int [][]boxes = new int[9][9];

• These are tracking matrices:

  • rows[r][val] == 1 → digit val+1 already appeared in row r

  • cols[c][val] == 1 → digit val+1 already appeared in column c

  • boxes[b][val] == 1 → digit val+1 already appeared in 3x3 box b

Each sub-array has 9 elements (0 to 8) to represent digits 1 to 9 (val = digit - 1).

---

for(int r = 0; r < 9; r++) {
for(int c = 0; c < 9; c++) {

• Traverse all cells in the 9x9 board using row r and column c.

---

if(board[r][c] == '.') {
    continue;
}

• Ignore empty cells (no digit placed yet).

🔁 The Line:

 val = board[r][c] - '1';

---

🔍 What It Does:

This line converts a character like '1', '2', ..., '9' into an integer between 0 and 8, which you can use as an array index.

---

🤔 Why Do We Need It?

You're working with a 9×9 Sudoku board, and you need to track whether a number has already been used in:

• a row → rows[9][9]

• a column → cols[9][9]

• a 3x3 box → boxes[9][9]

These arrays use 0-based indexing, meaning:

• Index 0 represents number 1

• Index 1 represents number 2

• ...

• Index 8 represents number 9

But the input board uses characters like '5', not numbers!

---

💡 So Line 12 Bridges This Gap:

Let’s say you read '5' from the board. That's a character, and its ASCII value is 53.

Now '5' - '1' = 53 - 49 = 4

So you get:

val = 4 // which represents number 5 (0-based index)

This val = 4 is now used to mark/check the index in:

• rows[r][4]

• cols[c][4]

• boxes[boxIndex][4]

---

📦 Example:

Let's say you see '9' on the board.

javaCopyEditval = board[r][c] - '1'; 
// '9' - '1' = 56 - 49 = 7
// val = 8

So you're checking:

• Is the number 9 already in this row? → rows[r][8]

• Is the number 9 already in this column? → cols[c][8]

• Is the number 9 already in this box? → boxes[boxidx][8]

---

✅ Summary:

board[r][c] - '1' converts the character digit into a 0-based index, which you need to access the right cell in the rows, cols, and boxes arrays.

🔍 Code You're Referring To:

if(rows[r][val]==1){
    return false;
}
rows[r][val]=1;

if(cols[c][val]==1){
    return false;
}
cols[c][val]=1;

---

🧠 What These Lines Do:

• rows[r][val] tracks whether the number val+1 has already appeared in row r.

• cols[c][val] does the same for column c.

Both use 0-based indexing, meaning:

• If val = 3, you're referring to number 4 (because val = '4' - '1' = 3).

• If r = 0, it's row 0, the first row of the board.

---

📦 Let’s Say We're Processing board[0][1] = '4'

This means:

• We're in row 0, column 1

• val = '4' - '1' = 3

Now you check:

if(rows[0][3] == 1) return false;

This is asking:

"Has the number 4 already occurred in row 0?"

If yes → return false (invalid board)

If not → mark it as used:

rows[0][3] = 1;

Then, check the same for column:

if(cols[1][3] == 1) return false;
cols[1][3] = 1;

"Has number 4 already occurred in column 1?"

---

🧊 Physical Representation:

You can imagine it like this (initially, all values are 0):

🔹 rows Array (Tracks 9 rows, each row tracks digits 1–9)

rows[0] → [0, 0, 0, 0, 0, 0, 0, 0, 0] // Before inserting number 4
                      ↑
                val=3 → number 4

After:
rows[0] → [0, 0, 0, 1, 0, 0, 0, 0, 0]

🔹 cols Array (Tracks 9 columns, each column tracks digits 1–9)

cols[1] → [0, 0, 0, 0, 0, 0, 0, 0, 0] // Column 1
                      ↑
                val=3 → number 4

After:
cols[1] → [0, 0, 0, 1, 0, 0, 0, 0, 0]

---

🔄 Repetition:

This check-and-mark process repeats for every cell in the board that's not '.'.

---

❌ What Happens on Duplicate?

Let’s say later in the row you again find '4' (same value) at a different column.

Now rows[0][3] == 1, so this:

if(rows[0][3] == 1)

is true, and it returns false, indicating invalid Sudoku.

🧩 Problem3:Rotate Image

📖 Problem:

Code:

class Solution {
    public void rotate(int[][] matrix) {
        int n=matrix.length;
        for(int i=0;i<n;i=i+1){
             for(int j=i+1;j<n;j++){
                 int temp=matrix[i][j];//[0][1]
                matrix[i][j]=matrix[j][i];
                 matrix[j][i]=temp;
             }
         }
         for(int i=0;i<n;i++){
             for(int j=0;j<n/2;j++){
                 int temp=matrix[i][j];
                 matrix[i][j]=matrix[i][n-1-j];
                 matrix[i][n-1-j]=temp;
            }
         }

💡 Key Concept

To rotate a matrix 90° clockwise:

1. Transpose the matrix
   → convert rows to columns
   → matrix[i][j] = matrix[j][i]

2. Reverse each row
   → swap elements from both ends of the row.

---

🔍 Code Explanation

int n = matrix.length;

• Get the size n of the square matrix.

---

🔁 Step 1: Transpose the Matrix

for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
        int temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
    }
}

🔄 Physical Meaning:

We swap the elements across the diagonal (top-left to bottom-right).

Example:

textCopyEditBefore Transpose:
[1 2 3]       After Transpose:
[4 5 6]  ==>  [1 4 7]
[7 8 9]       [2 5 8]
              [3 6 9]

We only loop through the upper triangle (j = i + 1) to avoid double-swapping.

---

🔁 Step 2: Reverse Each Row

for(int i = 0; i < n; i++){
    for(int j = 0; j < n / 2; j++){
        int temp = matrix[i][j];
        matrix[i][j] = matrix[i][n - 1 - j];
        matrix[i][n - 1 - j] = temp;
    }
}

🔄 Physical Meaning:

For every row, we swap elements from the left and right sides.

Example:

Before Row Reverse:
[1 4 7]       After Reverse:
[2 5 8]  ==>  [7 4 1]
[3 6 9]       [8 5 2]
              [9 6 3]

---

✅ Final Result (90° Clockwise Rotation)

Original:

[1 2 3]
[4 5 6]
[7 8 9]

After rotation:

csharpCopyEdit[7 4 1]
[8 5 2]
[9 6 3]

---

🧠 Time and Space Complexity

• Time Complexity: O(n^2)

  • Two nested loops (transpose + reverse rows)

• Space Complexity: O(1)

  • Done in-place, no extra space used

Example:

🎯 Problem: Rotate 90° Clockwise

Given:

Input Matrix:
[1 2 3]
[4 5 6]
[7 8 9]

---

🔁 Step 1: Transpose the Matrix

Swap elements across the diagonal (i.e., matrix[i][j] with matrix[j][i] for j > i)

We'll perform these swaps:

• (0,1) ↔ (1,0): swap 2 and 4

• (0,2) ↔ (2,0): swap 3 and 7

• (1,2) ↔ (2,1): swap 6 and 8

🔄 Transposed Matrix:

[1 4 7]
[2 5 8]
[3 6 9]

---

🔁 Step 2: Reverse Each Row

Reverse every row by swapping start and end elements.

Row 0:

[1 4 7] → [7 4 1]

Row 1:

[2 5 8] → [8 5 2]

Row 2:

[3 6 9] → [9 6 3]

---

✅ Final Rotated Matrix:

[7 4 1]
[8 5 2]
[9 6 3]

---

🔄 Full Visual Summary

[4 5 6]
[7 8 9] | | After Transpose | [1 4 7]
[2 5 8]
[3 6 9] | | After Row Reverse | [7 4 1]
[8 5 2]
[9 6 3] |

Method 2:

for(int i=0;i<n/2;i++){
            for(int j=i;j<n-i-1;j++){
                int del=j-i;
                int curr=matrix[i][j];
                int next=matrix[i+del][n-1-i];
                matrix[i+del][n-1-i]=curr;
                curr=next;

                next=matrix[n-i-1][n-i-1-del];
                matrix[n-i-1][n-i-1-del]=curr;
                curr=next;

                next=matrix[n-i-1-del][i];
                matrix[n-i-1-del][i]=curr;
                curr=next;
                matrix[i][j]=curr;
            }
        }

Steps:

Step 1:

📌 If we rotate the following matrix 90 degrees clockwise, we obtain the desired output.

Step 2:

🔁 Cycle Rotation Approach (5x5 Matrix)

To rotate the matrix 90 degrees clockwise, we use the cycle rotation technique. In this method, we rotate four elements at a time—each forming a cycle—starting from the outermost layer and moving inward.

As shown in the image:

• The value at index [0][0] moves to [0][4]

• The value at [0][4] shifts to [4][4]

• The value at [4][4] moves to [4][0]

• Finally, the value at [4][0] comes back to [0][0]

This completes one full cycle of rotation for the outermost layer.

👉 The same process is repeated for all other index positions in the current layer, and then the algorithm moves inward to rotate the inner layers similarly.

This approach ensures an in-place rotation without using any extra space, making it efficient in terms of both time and space complexity.

📸 Step Diagram of Cycle Rotation

In the image above, you can see a clear visual representation of how cycle rotation works in a 5×5 matrix. Each value from one corner is passed to the next in a circular fashion, until the rotation is complete.

---

🔄 Understanding the Loop Logic in Cycle Rotation

When implementing the 90-degree rotation of a matrix using cycle rotation, it's essential to correctly set the bounds of the nested loops to avoid duplicate or missed rotations.

🔹 Outer and Inner Loop Purpose

• The outer loop (i) represents the layer we are rotating (from the outermost to the innermost).

• The inner loop (j) goes through the elements in the top row of the current layer that are to be rotated.

🔹 Why j < n - i - 1?

Let’s understand this using a 5×5 matrix:

✅ When i = 0 (outermost layer):

We are rotating elements from top-left to top-right excluding the last element (because it will already be rotated by the cycle itself).
Hence, j should iterate through indices 0, 1, 2, 3 — i.e., total n - 2*i - 1 elements.

✅ When i = 1 (second layer):

Now we go one layer inside. j should go from 1 to 3, i.e., n - i - 1 = 3.

If you incorrectly write:

for(int j = 1; j < n - i - 1; j++)

you will skip the first element of each layer, resulting in incomplete rotation.

✅ Correct Loop Structure:

for(int i = 0; i < n / 2; i++) {
    for(int j = i; j < n - i - 1; j++) {
        // Perform the 4-way cyclic rotation
    }
}

This ensures that all necessary elements are rotated once and only once, achieving a proper 90-degree clockwise rotation of the matrix in place.

🧠 Deriving the Formula for 4-Way Cycle Rotation

Let’s understand how the indices rotate in a clockwise cycle for a matrix. We'll derive the formulas for each new position based on the current index [i][j].

📌 Consider this cycle:

We’ll track the following movement (in a clockwise 90° rotation):

[i1][j1] → [i2][j2] → [i3][j3] → [i4][j4] → back to [i1][j1]

Let’s assume one example cycle:

[1][4] → [4][5] → [5][2] → [2][1] → back to [1][4]

Now, we’ll derive each index step-by-step assuming:

• n = matrix.length

• i = current layer

• j = current element in the layer

• delta = j - i (distance from the diagonal)

---

🔸 Step 1: Start with [i][j]

Let’s denote this as:
[i1][j1] = [i][j]

This is the current element you're rotating.

---

🔸 Step 2: Move to [i2][j2] (Right → Down)

Now the current value will move to the element on the right boundary.

To find the new row and column:

• Row: This increases from top to bottom. Since we are going to the outermost column, it becomes i + delta
  → i2 = i + delta

• Column: The last column is n - 1 - i
  → j2 = n - 1 - i

✅ So:
[i2][j2] = [i + delta][n - 1 - i]

---

🔸 Step 3: Move to [i3][j3] (Bottom → Left)

Now we are going from the right boundary to the bottom row.

• Row: We’re now at the last row of the current layer → i3 = n - 1 - i

• Column: We move backward, decreasing the column →
  j3 = n - 1 - i - delta

✅ So:
[i3][j3] = [n - 1 - i][n - 1 - i - delta]

---

🔸 Step 4: Move to [i4][j4] (Left → Up)

Now we go from the bottom row to the left boundary.

• Row: We are going up → i4 = n - 1 - i - delta

• Column: This returns to the first column of the layer → j4 = i

✅ So:
[i4][j4] = [n - 1 - i - delta][i]

---

🔄 Cycle Summary (General Formula)

From a starting point [i][j], we rotate through:

Where delta = j - i

---

✅ Implementation Insight

This is why your cycle rotation code inside the nested loop looks like this:

int delta = j - i;

int curr = matrix[i][j];
int next = matrix[i + delta][n - 1 - i];
matrix[i + delta][n - 1 - i] = curr;
curr = next;

next = matrix[n - 1 - i][n - 1 - i - delta];
matrix[n - 1 - i][n - 1 - i - delta] = curr;
curr = next;

next = matrix[n - 1 - i - delta][i];
matrix[n - 1 - i - delta][i] = curr;
matrix[i][j] = next;

Problem 4: Reverse String

Problem:

class Solution {
    public void reverseString(char[] s) {
        int i=0;
        int j=s.length-1;
        while(i<=j){
            char temp=s[i];
            s[i]=s[j];
            s[j]=temp;
            i=i+1;
            j=j-1;
        }
    }
}

🧠 Approach (Two-Pointer Technique):

We use two pointers to reverse the string:

• One pointer i starts from the beginning of the array.

• Another pointer j starts from the end of the array.

• Swap the characters at these two positions and move the pointers towards each other until they meet.

• 🔍 Dry Run Example:

  Suppose:
  s = ['h','e','l','l','o']

  | Step | i | j | s[i] | s[j] | Result | | --- | --- | --- | --- | --- | --- | | 1 | 0 | 4 | 'h' | 'o' | ['o','e','l','l','h'] | | 2 | 1 | 3 | 'e' | 'l' | ['o','l','l','e','h'] | | 3 | 2 | 2 | 'l' | 'l' | (No change, mid reached) |

  Final Output: ['o','l','l','e','h']

✅ Conclusion

Solving these foundational problems from the 90-Day DSA Sheet has significantly improved my understanding of problem-solving techniques. From mastering hashmaps in Two Sum, understanding validity checks in Sudoku, applying matrix transformations for image rotation, to learning how to reverse strings using two-pointer approach—each challenge helped sharpen my logic and approach towards Data Structures and Algorithms.

I’m truly grateful to CTO Bhaiya (Anuj Kumar Sharma) on YouTube for curating such an amazing and structured DSA roadmap. His explanations made even the toughest concepts feel approachable and logical. I highly recommend fellow learners to follow his 90-Day plan and videos.

This is just the beginning, and I’m excited to continue this journey, one problem at a time! Stay tuned for more blog posts where I’ll share solutions, diagrams, and insights as I progress through this DSA sheet.