284. Two Pointers Problem from Leetcode — Part 1

Photo by Wolfgang Hasselmann on Unsplash

633. Sum of Square Numbers

Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

Example 1:

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: c = 3
Output: false

Constraints:

• 0 <= c <= 231 - 1

public class SumOfSquareNumbers {
    public boolean judgeSquareSum(int c) {
        // Start with two pointers, one at 0 and the other at the square root of c
        long left = 0;
        long right = (long) Math.sqrt(c);

        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) {
                return true;  // Found a and b such that a^2 + b^2 = c
            } else if (sum < c) {
                left++;  // Increase the sum by moving the left pointer to the right
            } else {
                right--;  // Decrease the sum by moving the right pointer to the left
            }
        }

        return false;  // No such pair found
    }

    public static void main(String[] args) {
        SumOfSquareNumbers solution = new SumOfSquareNumbers();
        
        // Test cases
        int c1 = 5;
        int c2 = 3;

        System.out.println("Input: " + c1 + " Output: " + solution.judgeSquareSum(c1));  // Expected: true
        System.out.println("Input: " + c2 + " Output: " + solution.judgeSquareSum(c2));  // Expected: false
    }
}

Time Complexity

The algorithm uses a two-pointer technique to find two integers a and b such that a^2+b^2=c.

1. Initialization of Pointers:

• The left pointer starts at 0.
• The right pointer starts at c​.

2. While Loop:

• The loop continues as long as left is less than or equal to right.
• In each iteration, we calculate the sum of the squares of left and right.
• Depending on the comparison of the sum with c, we either increment left or decrement right.

The key observation here is that the range of left and right is from 0 to c.

• In the worst case, both left and right will traverse the entire range from 0 to c​.
• Each step of the while loop involves a constant amount of work: calculating the sum and performing a comparison.

Thus, the total number of iterations of the while loop is bounded by c.

Time Complexity: O(c)

Space Complexity

The space complexity of an algorithm represents the amount of memory space required relative to the input size.

1. Auxiliary Space:

• The algorithm uses a constant amount of extra space for the pointers left and right, as well as for the variable sum.

2. Input Space:

• The input c is a single integer, so its space requirement is O(1).

Space Complexity: O(1)

Summary

Time Complexity: O(c)

• This is because we iterate through potential values of a and b from 0 to c​, and each iteration involves constant time operations.

Space Complexity: O(1)

• The algorithm uses a constant amount of space regardless of the size of c.

Discussion

The algorithm is efficient for large values of c, particularly because the time complexity grows only as the square root of c, not linearly or quadratically. This makes the algorithm suitable for handling the upper constraint 0 ≤ c ≤ 2^31−1.

For example, if c is as large as 2^31−1, the maximum value of c​ is approximately 2^15.5 ≈ 46340. Thus, the algorithm will perform at most around 46340 iterations in the worst case, which is manageable for modern computing systems.

5. Longest Palindromic Substring

Given a string s, return the longest

palindromic

substring

in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

public class LongestPalindromicSubstring {

    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i); // Odd length palindrome
            int len2 = expandAroundCenter(s, i, i + 1); // Even length palindrome
            int len = Math.max(len1, len2);
            
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        
        return R - L - 1;
    }

    public static void main(String[] args) {
        LongestPalindromicSubstring solution = new LongestPalindromicSubstring();

        // Test case 1
        String s1 = "babad";
        System.out.println("Input: " + s1 + " Output: " + solution.longestPalindrome(s1));  // Expected: "bab" or "aba"

        // Test case 2
        String s2 = "cbbd";
        System.out.println("Input: " + s2 + " Output: " + solution.longestPalindrome(s2));  // Expected: "bb"
    }
}

Explanation of the Code

1. Main Method:

• The main method creates an instance of the LongestPalindromicSubstring class and tests the longestPalindrome method with given inputs.

2. longestPalindrome Method:

Parameters: Takes a string s.

Returns: The longest palindromic substring in s.

Logic:

• It initializes start and end to keep track of the current longest palindromic substring.
• It iterates over each character in the string and considers two cases for possible palindromic centers:

1. A single character center (odd length palindrome).
2. Two consecutive characters center (even length palindrome).

• It calls the expandAroundCenter method for both cases and updates start and end if a longer palindrome is found.

3. expandAroundCenter Method:

Parameters: Takes the string s, and two integers left and right representing the center of the palindrome.

Returns: The length of the palindrome centered at left and right.

Logic:

• It expands around the center while the characters on both sides are equal.
• It returns the length of the palindrome found.

Complexity Analysis

1. Time Complexity:

• The longestPalindrome method runs in O(n^2) time, where n is the length of the string.
• This is because for each character (total n), we perform the expansion which in the worst case takes O(n).

2. Space Complexity:

• The space complexity is O(1) as we are using only a few extra variables for storing indices and lengths.

This solution efficiently finds the longest palindromic substring within the given constraints.

Hint 1: How can we reuse a previously computed palindrome to compute a larger palindrome?

To efficiently reuse previously computed palindromes for computing larger palindromes, we can use a dynamic programming approach. This method involves storing information about smaller palindromes and using that information to build larger palindromes.

The idea is to use a 2D boolean array dp where dp[i][j] is true if the substring s[i:j+1] is a palindrome. We can then use this information to determine if larger substrings are palindromes.

Steps for the Dynamic Programming Approach:

1. Initialization:

• Every single character is a palindrome by itself (dp[i][i] = true).
• Check for two-character palindromes and initialize them (dp[i][i+1] = true if s.charAt(i) == s.charAt(i+1)).

2. Build the dp table:

• For substrings longer than two characters, use the recurrence relation: dp[i][j] = true if s.charAt(i) == s.charAt(j) and dp[i+1][j-1] is true.

3. Track the longest palindrome:

• Keep track of the start and end indices of the longest palindromic substring found.

public class LongestPalindromicSubstring {

    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;

        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLength = 1;

        // All substrings of length 1 are palindromes
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // Check for sub-strings of length 2.
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                start = i;
                maxLength = 2;
            }
        }

        // Check for lengths greater than 2. k is the length of substring
        for (int k = 3; k <= n; k++) {
            // Fix the starting index
            for (int i = 0; i < n - k + 1; i++) {
                // Get the ending index of substring from starting index i and length k
                int j = i + k - 1;

                // Checking for sub-string from i to j if s.charAt(i) == s.charAt(j)
                // and the substring s[i+1:j-1] is a palindrome
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;

                    if (k > maxLength) {
                        start = i;
                        maxLength = k;
                    }
                }
            }
        }

        return s.substring(start, start + maxLength);
    }

    public static void main(String[] args) {
        LongestPalindromicSubstring solution = new LongestPalindromicSubstring();

        // Test case 1
        String s1 = "babad";
        System.out.println("Input: " + s1 + " Output: " + solution.longestPalindrome(s1));  // Expected: "bab" or "aba"

        // Test case 2
        String s2 = "cbbd";
        System.out.println("Input: " + s2 + " Output: " + solution.longestPalindrome(s2));  // Expected: "bb"
    }
}

Explanation of the Code

1. Initialization:

• Initialize a 2D boolean array dp where dp[i][j] is true if the substring s[i:j+1] is a palindrome.
• Set all single character substrings to be palindromes (dp[i][i] = true).

2. Check for Two-Character Palindromes:

• Iterate through the string and set dp[i][i+1] to true if s.charAt(i) == s.charAt(i+1).
• Update the start and maxLength if a two-character palindrome is found.

3. Build the dp Table:

• For substrings of length greater than 2, use the previously computed values to determine if the substring s[i:j+1] is a palindrome.
• The substring s[i:j+1] is a palindrome if s.charAt(i) == s.charAt(j) and dp[i+1][j-1] is true.
• Update the start and maxLength if a longer palindrome is found.

4. Return the Longest Palindromic Substring:

• Extract the substring from start to start + maxLength.

Complexity Analysis

1. Time Complexity:

• The algorithm runs in O(n^2) time, where nn is the length of the string. This is because we fill an n×n table and each cell is computed in constant time.

2. Space Complexity:

• The space complexity is O(n^2) due to the 2D dp array used to store the palindrome information.

This dynamic programming approach efficiently finds the longest palindromic substring and reuses previously computed results to build larger palindromes.