Leatcode Java – suresh tuts

Problem Solving through Java

Roman to Integer

import java.util.HashMap;
import java.util.Map;

class Solution {
public int romanToInt(String s) {
Map<Character, Integer> romanMap = new HashMap<>();
romanMap.put(‘I’, 1);
romanMap.put(‘V’, 5);
romanMap.put(‘X’, 10);
romanMap.put(‘L’, 50);
romanMap.put(‘C’, 100);
romanMap.put(‘D’, 500);
romanMap.put(‘M’, 1000);

int sum = 0;
int prevValue = 0;

for (int i = s.length() – 1; i >= 0; i–) {
int value = romanMap.get(s.charAt(i));
if (value < prevValue) {
sum -= value;
} else {
sum += value;
}
prevValue = value;
}
return sum;
}
}

Line-by-line explanation

Defines a public method that takes a Roman numeral string s and returns an integer.

public int romanToInt(String s)

Creates a Map from Roman character to its integer value. This lets the code quickly convert a character (like 'X') to 10.

Map<Character, Integer> romanMap = new HashMap<>();
romanMap.put(‘I’, 1);
romanMap.put(‘V’, 5);
romanMap.put(‘X’, 10);
romanMap.put(‘L’, 50);
romanMap.put(‘C’, 100);
romanMap.put(‘D’, 500);
romanMap.put(‘M’, 1000);

Initializes sum (the running total) and prevValue (value of the previously processed character, i.e., the character immediately to the right in the original string). prevValue starts at 0 because nothing has been processed yet.

int sum = 0;
int prevValue = 0;

Iterates over the string from the last character to the first. value is the integer mapping for the current Roman character.

for (int i = s.length() – 1; i >= 0; i–) {
int value = romanMap.get(s.charAt(i));

if (value < prevValue) {
sum -= value;
} else {
sum += value;
}

prevValue = value;
}
return sum;
}

If current value is less than prevValue (meaning this Roman character should be subtracted according to Roman rules), subtract it from sum.

Otherwise, add it to sum.

Update prevValue to the current value for the next iteration, finish loop and return sum.

Worked example — `"MCMIV"` (which is 1904)

Process right-to-left:

char 'V' → value = 5. prevValue = 0 → 5 >= 0 → sum = 0 + 5 = 5. Set prevValue = 5.
char 'I' → value = 1. 1 < 5 → subtract → sum = 5 - 1 = 4. Set prevValue = 1.
char 'M' → value = 1000. 1000 >= 1 → add → sum = 4 + 1000 = 1004. Set prevValue = 1000.
char 'C' → value = 100. 100 < 1000 → subtract → sum = 1004 - 100 = 904. Set prevValue = 100.
char 'M' → value = 1000. 1000 >= 100 → add → sum = 904 + 1000 = 1904. Done → return 1904.

Integer to Roman

public String intToRoman(int num) {

int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

String[] symbols = {“M”, “CM”, “D”, “CD”, “C”, “XC”, “L”, “XL”, “X”, “IX”, “V”, “IV”, “I”};

StringBuilder sb = new StringBuilder();

for (int i = 0; i < values.length; i++) {

while (num >= values[i]) {

num -= values[i];

sb.append(symbols[i]);

}

return sb.toString();

}

Line-by-line explanation

public String intToRoman(int num) {

Method signature — takes an integer num, returns a Roman numeral String.

int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

Two parallel arrays:

values[i] is the integer value.
symbols[i] is the Roman string that represents that value.

They are ordered from largest to smallest

StringBuilder sb = new StringBuilder();

Creates a mutable StringBuilder to efficiently build the resulting Roman string.

for (int i = 0; i < values.length; i++) {
    while (num >= values[i]) {
        num -= values[i];
        sb.append(symbols[i]);
    }
}

Loop i over every value/symbol pair (from largest to smallest).
The while checks if the current values[i] fits into the remaining num.
- If yes, subtract that value from num and append the corresponding symbols[i].
- Repeat while the same symbol still fits (this handles repeats like 300 → "CCC").
Move on to the next smaller value when the current value no longer fits.

Because arrays include subtractive pairs, the algorithm automatically emits correct symbols like "IV", "IX", "CM", etc.

    return sb.toString();
}

Return the built Roman numeral string.

Worked example — `num = 1994`

Start: num = 1994, sb = "".

i=0 (1000, “M”): 1994 >= 1000 → subtract 1000 → num = 994; append “M” → sb = "M". Now 994 < 1000 so exit while.
i=1 (900, “CM”): 994 >= 900 → subtract 900 → num = 94; append “CM” → sb = "MCM".
i=2 (500, “D”): 94 < 500 skip.
i=3 (400, “CD”): 94 < 400 skip.
i=4 (100, “C”): 94 < 100 skip.
i=5 (90, “XC”): 94 >= 90 → subtract 90 → num = 4; append “XC” → sb = "MCMXC".
i=6..10 values > 4 skip until i=11 (4, “IV”): 4 >= 4 → subtract 4 → num = 0; append “IV” → sb = "MCMXCIV".
Loop ends, return "MCMXCIV". That’s the correct Roman for 1994.

longest substring without repeating characters

public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> charIndexMap = new HashMap<>();
        int maxLength = 0;
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);
            if (charIndexMap.containsKey(currentChar) && charIndexMap.get(currentChar) >= left) {
                left = charIndexMap.get(currentChar) + 1;
            }
            charIndexMap.put(currentChar, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

What each variable means

charIndexMap: remembers the most recent index where each character appeared.
left: start index of the current window (substring with no repeats).
right: end index of the current window, expanded in the for loop.
maxLength: best (longest) window size seen so far.

How it works (sliding window logic)

Start with an empty window (left = 0), and expand right from 0 to s.length()-1.
For each right, read currentChar = s.charAt(right).
If currentChar has appeared before and its last seen index is inside the current window (i.e., charIndexMap.get(currentChar) >= left):
- Move the start of the window left just past that previous occurrence:
  left = charIndexMap.get(currentChar) + 1.
- This removes the duplicate from the window.
Update the last seen index of currentChar:
charIndexMap.put(currentChar, right).
Update the best length:
maxLength = Math.max(maxLength, right - left + 1).
After the loop, return maxLength.

Mini trace example: `s = "abcabcbb"`

Step	right	currentChar	Seen & inside window?	left (after)	Window	maxLength
1	0	a	no	0	“a”	1
2	1	b	no	0	“ab”	2
3	2	c	no	0	“abc”	3
4	3	a	yes (idx 0 ≥ 0)	1	“bca”	3
5	4	b	yes (idx 1 ≥ 1)	2	“cab”	3
6	5	c	yes (idx 2 ≥ 2)	3	“abc”	3
7	6	b	yes (idx 4 ≥ 3)	5	“cb”	3
8	7	b	yes (idx 6 ≥ 5)	7	“b”	3

Pascal's triangle

public List<List<Integer>> generate(int numRows) {
   List<List<Integer>> triangle = new ArrayList<>();
   for (int row = 0; row < numRows; row++) {
      List<Integer> currentRow = new ArrayList<>();
      for (int col = 0; col <= row; col++) {
         if (col == 0 || col == row) {
            currentRow.add(1); // first & last element is always 1
         } else {
            int val = triangle.get(row - 1).get(col - 1) + triangle.get(row - 1).get(col);
            currentRow.add(val);
         }
      }
      triangle.add(currentRow);
   }
   return triangle;
}

Explanation

Initialization

List<List<Integer>> triangle = new ArrayList<>();

triangle is a list of lists, where each inner list represents a row in Pascal’s Triangle.

Outer loop: Iterating over rows

for (int row = 0; row < numRows; row++) {
List<Integer> currentRow = new ArrayList<>();

row runs from 0 to numRows - 1.
For each iteration, a new row (currentRow) is created.
If numRows = 5, the outer loop runs 5 times for rows 0 → 4.

Inner loop: Filling elements in a row

for (int col = 0; col <= row; col++) {

Each row has one more element than the previous row.

Row 0 → 1 element
Row 1 → 2 elements
Row 2 → 3 elements, etc.

First and Last elements = 1

if (col == 0 || col == row) {
currentRow.add(1);
}

In Pascal’s Triangle, the first and last elements of every row are always 1.

Example:
Row 0 → [1]
Row 1 → [1, 1]
Row 2 → [1, ?, 1]

Middle elements = Sum of two above elements

else {
int val = triangle.get(row - 1).get(col - 1) + triangle.get(row - 1).get(col);
currentRow.add(val);
}

For any middle element, it equals the sum of the two numbers above it from the previous row:
triangle[row][col]=triangle[row-1][col-1]+triangle[row-1][col]
To calculate the 2nd element in row 2 (col=1):
val = triangle[1][0] + triangle[1][1]
= 1 + 1
= 2

Add Current row to triangle

triangle.add(currentRow);

After filling the current row, it’s appended to the main triangle list.

Return the final triangle

return triangle;

When the loop ends, the full Pascal’s Triangle with numRows rows is returned.

Example:

Row	Calculation	Result
0	`[1]`	`[1]`
1	`[1, 1]`	`[1, 1]`
2	`1, (1+1), 1`	`[1, 2, 1]`
3	`1, (1+2), (2+1), 1`	`[1, 3, 3, 1]`
4	`1, (1+3), (3+3), (3+1), 1`	`[1, 4, 6, 4, 1]`

Final Triangle

[
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1]
]

Letter Combinations of a Phone Number.

private static final String[] KEYS = {

“”, // 0

“”, // 1

“abc”, // 2

“def”, // 3

“ghi”, // 4

“jkl”, // 5

“mno”, // 6

“pqrs”, // 7

“tuv”, // 8

“wxyz” // 9

};

public List<String> letterCombinations(String digits) {

List<String> result = new ArrayList<>();

if (digits == null || digits.length() == 0) {

return result;

}

backtrack(result, new StringBuilder(), digits, 0);

return result;

}

private void backtrack(List<String> result, StringBuilder current, String digits, int index) {

if (index == digits.length()) {

result.add(current.toString());

return;

}

String letters = KEYS[digits.charAt(index) – ‘0’];

for (char c : letters.toCharArray()) {

current.append(c);

backtrack(result, current, digits, index + 1);

current.deleteCharAt(current.length() – 1);

}

Explanation:

A single, shared (static) and unchangeable reference (final) map from digit → letters.
It mirrors old phone keypads: 2→abc, 3→def, … 9→wxyz.
Note: digits ‘0’ and ‘1’ are intentionally absent because they don’t map to letters.

Public method that users call

public List<String> letterCombinations(String digits) {
   List<String> result = new ArrayList<>();
   if (digits == null || digits.length() == 0) {
      return result; // no input → no combinations
   }
   backtrack(result, digits, "", 0);
   return result;
}

Creates a container result to collect all combinations.
Early return for null or empty input.
Starts the recursive search with:
- - current = new StringBuilder() (the partial string being built)
  - index = 0 (we’re at the first digit)
Backtracking core

Base case: when index reaches digits.length(), you’ve picked one letter for each digit → add the built string to result.
digits.charAt(index) - '0' converts the char digit (e.g., '2') to its int value (2) so we can index into KEYS.
Loop: try each possible letter for the current digit:
- choose: append(c) extends the current partial string.
- recurse: move to the next digit (index + 1).
- un-choose: remove the last char so we can try the next letter. This is the “backtrack” step.

Example: `digits = "23"`

Mappings:

2 → "abc"
3 → "def"

Call stack evolution (showing current and index):

backtrack("", index=0)
letters = "abc"
- Pick 'a' → current="a"
  2. backtrack("a", index=1)
  letters = "def"
  - Pick 'd' → "ad" → index=2 → base case → add "ad"
  - Backtrack to "a"
  - Pick 'e' → "ae" → base case → add "ae"
  - Backtrack to "a"
  - Pick 'f' → "af" → base case → add "af"
  - Backtrack to "" (after removing 'a')
- Pick 'b' → current="b"
  3. backtrack("b", index=1) → produces "bd", "be", "bf"
- Pick 'c' → current="c"
  4. backtrack("c", index=1) → produces "cd", "ce", "cf"

Final result = [ad, ae, af, bd, be, bf, cd, ce, cf].

Two Sum

public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

Step by step process

HashMap<Integer, Integer> map = new HashMap<>();
- Create a map from number value → its index seen so far while scanning the array.
- Example entry: if nums[3] == 11, map might contain {11 → 3}.
for (int i = 0; i < nums.length; i++) { ... }
- Walk through the array once, left to right.
int complement = target - nums[i];
- The number you’d need to pair with nums[i] to reach target.
- If target is 9 and nums[i] is 2, complement is 7.
if (map.containsKey(complement)) { ... }
- Have we already seen a number equal to complement earlier in the array?
- If yes, then that earlier index and current i form a valid pair.
return new int[]{map.get(complement), i};
- Return the pair of indices:
  - map.get(complement) → index of the previously seen complement
  - i → current index
- Returning immediately stops the function once the first valid pair is found.
map.put(nums[i], i);
- If no complement was found earlier, record the current value and index so it can serve as a complement for some future element.
throw new IllegalArgumentException("No two sum solution");
- If the loop ends without finding any pair, signal that there is no solution.

Example

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

Start: map = {}
i = 0, nums[0] = 2 → complement = 7
- map doesn’t contain 7 → put {2 → 0}
i = 1, nums[1] = 7 → complement = 2
- map does contain 2 at index 0 → return {0, 1}

Climbing Stairs

public int climbStairs(int n) {
int previousTwo = 0;
int previousOne = 1;

for (int step = 0; step < n; ++step) {
int current = previousTwo + previousOne;
previousTwo = previousOne;
previousOne = current;
}
return previousOne;
}

Explanation:

Ways to reach step n = ways to reach n-1 + ways to reach n-2.
(From n-1 you take 1 step; from n-2 you take 2 steps.)

Variables

previousTwo = ways to reach the step two behind the current step.
previousOne = ways to reach the step one behind the current step.

previousTwo = 0; // F(0)
previousOne = 1; // F(1)

This mirrors Fibonacci seeds so that the loop builds up F(1), F(2), ..., F(n).

For each simulated “step” from 0 to n-1:

current = previousTwo + previousOne;
(ways to current = ways to previousOne + ways to previousTwo)
Shift the window forward:
- previousTwo = previousOne;
- previousOne = current;

When the loop finishes, previousOne holds F(n) → the number of ways to climb n stairs.

iteration	current = p2 + p1	new p2	new p1
start	—	0	1
step 0	0 + 1 = 1	1	1
step 1	1 + 1 = 2	1	2
step 2	1 + 2 = 3	2	3
step 3	2 + 3 = 5	3	5
step 4	3 + 5 = 8	5	8
Return 8.

Length of last word

public int lengthOfLastWord(String s) {
        int endIndex = s.length() - 1;
    
        // Skip trailing spaces from the end
        while (endIndex >= 0 && s.charAt(endIndex) == ' ') {
            endIndex--;
        }
      
        int startIndex = endIndex;
       
        // Move backward to find the start of the last word
        while (startIndex >= 0 && s.charAt(startIndex) != ' ') {
            startIndex--;
        }
       
        // Length of the last word is the difference between end and start indices
        return endIndex - startIndex;
    }

Step by step

Start from the last character

endIndex = s.length() - 1 points at the final character.

Skip any trailing spaces

While endIndex points to a space, move it left (endIndex--).
After this loop:
- If the string has non-space chars, endIndex now points to the last character of the last word.
- If the string is all spaces or empty, endIndex becomes -1.

Mark where the last word currently ends

startIndex = endIndex (temporary marker to walk left over the word).

Walk left until a space or start of string

While startIndex is within bounds and not a space, decrement it.
When this finishes, startIndex points just before the last word:
- Either it’s -1 (we hit the beginning), or it’s at a space.

Compute length

The last word spans indices (startIndex+1) through endIndex inclusive.
Length = endIndex - startIndex.

Example 1: `"Hello World "`

Start: endIndex = 12 (last char, a space)
Skip spaces: 12→11 (space) → 10 ('d'), stop.
startIndex = 10
Walk word: 10:d→9:l→8:r→7:o→6:W, then 5 is a space → stop at 5.
Return 10 - 5 = 5.

Example 2: `" fly me to the moon "`

Trailing spaces skipped to the 'n' in "moon" at endIndex.
Walk back over "moon" to the space before it.
Return 4.

Example 3: `"a"`

endIndex = 0 (not space)
startIndex walks to -1
Return 0 - (-1) = 1.

Example 4: `" "` (only spaces)

endIndex decrements to -1
startIndex = -1
Second loop doesn’t run
Return -1 - (-1) = 0 → last word length is 0 (no word).

Strong Password Checker

public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>(Collections.nCopies(rowIndex + 1, 1));
        for (int i = 1; i < rowIndex + 1; i++) {
            for (int j = i - 1; j > 0; j--) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }
        return row;
    }

Step by Step Process

Step 1: Start with all 1s

new ArrayList<>(Collections.nCopies(rowIndex + 1, 1))

Creates a list of length rowIndex + 1 filled with 1s.
In Pascal’s Triangle, each row starts and ends with 1, so this is a good base.

Step 2: Build the row in-place (right → left)

for (int i = 1; i < rowIndex + 1; i++) {
    for (int j = i - 1; j > 0; j--) {
        row.set(j, row.get(j) + row.get(j - 1));
    }
}

Outer loop i goes over rows conceptually (from row 1 up to rowIndex).
Inner loop updates the current row from right to left:
- row[j] = row[j] + row[j - 1]
- This matches Pascal’s rule: C(i, j) = C(i-1, j) + C(i-1, j-1).
- Going right-to-left is crucial so we don’t overwrite row[j-1] before it’s used (in-place DP).
The loop bounds keep edges as 1:
- j > 0 means we never touch index 0 (left edge remains 1).
- Because j starts at i-1, we only update positions that exist for the current conceptual row; the right edge at index i stays 1.

return row;

Now we get the rowIndex-th Pascal row, e.g.:

rowIndex = 0 → [1]
rowIndex = 1 → [1, 1]
rowIndex = 4 → [1, 4, 6, 4, 1]

example (`rowIndex = 4`)

Start: [1, 1, 1, 1, 1]

i=1: (j=0 none) → [1, 1, 1, 1, 1]
i=2: j=1 → row[1]=1+1=2 → [1, 2, 1, 1, 1]
i=3: j=2 → 1+2=3; j=1 → 2+1=3 → [1, 3, 3, 1, 1]
i=4: j=3 → 1+3=4; j=2 → 3+3=6; j=1 → 3+1=4 → [1, 4, 6, 4, 1]

That’s the exact Pascal row.

Problem Solving through Java

Line-by-line explanation

Worked example — "MCMIV" (which is 1904)

Line-by-line explanation

Worked example — num = 1994

What each variable means

How it works (sliding window logic)

Mini trace example: s = "abcabcbb"

Explanation

Initialization

Outer loop: Iterating over rows

Inner loop: Filling elements in a row

First and Last elements = 1

Middle elements = Sum of two above elements

Add Current row to triangle

Return the final triangle

Example:

Final Triangle

Explanation:

Public method that users call

Example: digits = "23"

Step by step process

Example

Explanation:

Variables

Step by step

Example 1: "Hello World "

Example 2: " fly me to the moon "

Example 3: "a"

Example 4: " " (only spaces)

Step by Step Process

example (rowIndex = 4)

Worked example — `"MCMIV"` (which is 1904)

Worked example — `num = 1994`

Mini trace example: `s = "abcabcbb"`

Example: `digits = "23"`

Example 1: `"Hello World "`

Example 2: `" fly me to the moon "`

Example 3: `"a"`

Example 4: `" "` (only spaces)

example (`rowIndex = 4`)