Day 48: Competitive Programming Journal

Date: November 11, 2024
Hello Everyone,

Today marks Day 48 of my competitive programming journey. Here's what I worked on today:

What I Did Today:
I solved two problems: Search an element in a matrix sorted row-wise and column-wise and Find the longest palindromic substring in a string.

1. Search an element in a matrix sorted row-wise and column-wise:
Problem:

You are given an n x m matrix where each row is sorted in ascending order, and each column is also sorted in ascending order. Find whether a given element exists in the matrix.

Explanation:

• Start searching from the top-right corner of the matrix.
• If the current element is larger than the target, move left.
• If the current element is smaller than the target, move down.

Implementation:

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    int i = 0, j = cols - 1; 

    while (i < rows && j >= 0) {
        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] > target) {
            j--;
        } else {
            i++; 
        }
    }

    return false;
}

2. Find the longest palindromic substring in a string:
Problem:
Given a string, find the longest substring that is a palindrome.

Explanation:

• Use the "expand around center" approach.
• Treat each character as a potential center of a palindrome.
• Check for odd- and even-length palindromes by expanding around the center.

Implementation:

string longestPalindrome(string s) {
    int n = s.length();
    int start = 0, maxLength = 1;

    for (int i = 0; i < n; i++) {
        int low = i, high = i;
        while (low >= 0 && high < n && s[low] == s[high]) {
            if (high - low + 1 > maxLength) {
                start = low;
                maxLength = high - low + 1;
            }
            low--;
            high++;
        }

        low = i, high = i + 1;
        while (low >= 0 && high < n && s[low] == s[high]) {
            if (high - low + 1 > maxLength) {
                start = low;
                maxLength = high - low + 1;
            }
            low--;
            high++;
        }
    }

    return s.substr(start, maxLength);
}

Reflection:
Today’s problems challenged my logical thinking, especially in understanding how to navigate a sorted matrix efficiently. The palindrome problem, though classic, is always enjoyable as it combines multiple concepts like pointers and substring operations.

Stay tuned for more updates, and happy coding!