Array and String Algorithms: Core Problem Solutions

Longest Substring Without Repeating Characters

This problem involves finding the length of the longest substring in a given string that does not contain any repeating characters. A common approach uses a sliding window technique with a Set to efficiently track unique characters.

Strategy:

• Utilize a Set to store characters within the current window.
• Iterate through the string with a right pointer, adding characters to the Set.
• If a duplicate character is encountered, move the left pointer forward, removing characters from the Set, until the duplicate is no longer present.
• At each step, update the maximum length found.

Java Implementation Snippet

class Solution {
    public int findLongestSubstringWithoutRepeatingCharacter(String str) {
        Set<Character> charSet = new HashSet<>();
        int leftChar = 0;
        int rightChar = 0;
        int maxLength = 0;
        while (rightChar < str.length()) {
            if (!charSet.contains(str.charAt(rightChar))) {
                charSet.add(str.charAt(rightChar));
                maxLength = Math.max(maxLength, charSet.size());
                rightChar++; // Advance the right pointer
            } else {
                charSet.remove(str.charAt(leftChar));
                leftChar++;
            }
        }
        return maxLength;
    }
}

Container With Most Water

Given an integer array height of length n, there are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). The goal is to find two lines that, together with the x-axis, form a container that can store the most water. Return the maximum amount of water a container can store.

Notice: You may not slant the container.

Java Implementation Snippet

class Solution {
    public int maxArea(int[] height) {
        int start = 0;
        int end = height.length - 1;
        int maxArea = 0; // Initialize maxArea
        while (start < end) {
            int area = Math.min(height[start], height[end]) * (end - start); // Added semicolon
            maxArea = Math.max(maxArea, area);
            if (height[start] < height[end]) {
                start++;
            } else {
                end--;
            }
        }
        return maxArea;
    }
}

3Sum Problem

The 3Sum problem asks to find all unique triplets in the array which give the sum of zero.

Solution Strategy:

1. First, sort the array. This is crucial for the two-pointer approach and for easily skipping duplicate elements.
2. Iterate through the sorted array, fixing one number (e.g., arr[i]).
3. For each fixed number, use two pointers (left and right) to find the remaining two numbers that sum to -arr[i].
4. Adjust left and right pointers based on whether the current sum is less than, greater than, or equal to the target.
5. Implement logic to skip duplicate elements for all three pointers (i, left, and right) to ensure unique triplets in the result.

Java Implementation Snippet

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] arr) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(arr); // Sort the array

        for (int i = 0; i < arr.length - 2; i++) {
            // Skip duplicate for 'i'
            if (i > 0 && arr[i] == arr[i - 1]) {
                continue;
            }

            int target = -arr[i]; // Target for the two pointers
            int p1 = i + 1;
            int p2 = arr.length - 1;

            while (p1 < p2) {
                int currentSum = arr[p1] + arr[p2];

                if (currentSum == target) {
                    result.add(Arrays.asList(arr[i], arr[p1], arr[p2]));
                    p1++;
                    p2--;
                    // Skip duplicates for p1 and p2
                    while (p1 < p2 && arr[p1] == arr[p1 - 1]) {
                        p1++;
                    }
                    while (p1 < p2 && arr[p2] == arr[p2 + 1]) {
                        p2--;
                    }
                } else if (currentSum < target) {
                    p1++;
                } else { // currentSum > target
                    p2--;
                }
            }
        }
        return result;
    }
}

Next Permutation Algorithm

The problem asks to find the next lexicographically greater permutation of numbers. If no such permutation exists, it must rearrange the numbers into the lowest possible order (i.e., sorted in ascending order).

Algorithm Steps:

1. Find the Pivot: Start from the right and find the first element nums[i] that is smaller than nums[i+1]. This is the "pivot". If no such element is found, the array is in descending order, and its next permutation is the sorted (ascending) array.
2. Find the Swap Element: If a pivot is found, again start from the right and find the first element nums[j] that is greater than nums[i] (the pivot).
3. Swap: Swap nums[i] and nums[j].
4. Reverse Suffix: Reverse the subarray starting from i + 1 to the end of the array. This ensures the smallest possible permutation after the swap.

Rotate Image Matrix

Given an n x n 2D matrix representing an image, the task is to rotate the image by 90 degrees clockwise. This operation must be performed in-place, meaning you modify the input 2D matrix directly.

Common Strategy:

1. Transpose the matrix: Swap matrix[i][j] with matrix[j][i] for all i < j.
2. Reverse each row: After transposing, reverse each row of the matrix. This will result in a 90-degree clockwise rotation.