Day 43: Competitive Programming Journal

Date: November 4, 2024.
Hello Everyone,

Today marks Day 43 of my competitive programming journey, and I’m here to share my progress.

What I Did Today:
I worked on two problems: Find the maximum product of two integers in an array and Rearrange an array such that the maximum and minimum elements alternate.

1. Find the maximum product of two integers in an array:
Problem:
Given an array of integers, find the maximum product that can be obtained by multiplying any two distinct elements.

Explanation:

• Sort the array and calculate the product of the two largest numbers.
• Alternatively, consider the product of the two smallest numbers (if they’re negative) since their product can be positive and larger than other combinations.

Here’s the implementation:

int maxProduct(const vector<int>& arr) {
    int n = arr.size();
    if (n < 2) {
        cout << "Array should have at least two elements." << endl;
        return -1;
    }

    int max1 = INT_MIN, max2 = INT_MIN;
    int min1 = INT_MAX, min2 = INT_MAX;

    for (int num : arr) {
        if (num > max1) {
            max2 = max1;
            max1 = num;
        } else if (num > max2) {
            max2 = num;
        }

        if (num < min1) {
            min2 = min1;
            min1 = num;
        } else if (num < min2) {
            min2 = num;
        }
    }

    return max(max1 * max2, min1 * min2);
}

2. Rearrange an array such that the maximum and minimum elements alternate:

Problem:
Rearrange an array so that the largest element is followed by the smallest, then the second largest, then the second smallest, and so on.

Explanation:

• Sort the array.
• Use two pointers: one starting from the beginning (smallest) and the other from the end (largest). Alternate between them to create the rearranged array.

Here’s the implementation:

vector<int> rearrangeArray(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    vector<int> result;

    int i = 0, j = arr.size() - 1;
    while (i <= j) {
        if (j > i) result.push_back(arr[j--]); 
        if (i <= j) result.push_back(arr[i++]);
    }

    return result;
}

Reflection:
Today’s problems were engaging and involved some sorting techniques and pointer manipulation. Rearranging the array helped me understand how to utilize two-pointer methods effectively, while finding the maximum product highlighted the importance of edge cases like negative numbers.

Stay tuned for more updates, and feel free to share your thoughts and experiences!