Day 54: Competitive Programming Journal

Date: November 19, 2024
Hello Everyone,

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

What I Did Today:
I tackled two problems: Find the smallest range covering elements from k sorted lists (Sliding Window) and Find the length of the shortest unsorted subarray in an array.

1. Find the smallest range covering elements from k sorted lists (Sliding Window):
Problem:
Given k sorted lists, find the smallest range that includes at least one number from each of the k lists.

Explanation:

• Use a min-heap to maintain the current minimum of the current window and track which list each element belongs to.
• Iterate through each list, updating the range and ensuring no overlap.

Implementation:

vector<int> findSmallestRange(vector<vector<int>>& nums) {
    int k = nums.size();
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
    int rangeStart = 0, rangeEnd = INT_MAX;
    int currentMax = INT_MIN;

    for (int i = 0; i < k; ++i) {
        minHeap.push({nums[i][0], i, 0});
        currentMax = max(currentMax, nums[i][0]);
    }

    while (true) {
        auto [minVal, listIndex, elementIndex] = minHeap.top(); minHeap.pop();
        if (currentMax - minVal < rangeEnd - rangeStart) {
            rangeStart = minVal;
            rangeEnd = currentMax;
        }

        if (elementIndex + 1 < nums[listIndex].size()) {
            int nextVal = nums[listIndex][elementIndex + 1];
            minHeap.push({nextVal, listIndex, elementIndex + 1});
            currentMax = max(currentMax, nextVal);
        } else {
            break;
        }
    }

    return {rangeStart, rangeEnd};
}

2. Find the length of the shortest unsorted subarray in an array:
Problem:
Given an array, find the length of the shortest subarray that, if sorted, would sort the entire array.

Explanation:

• Identify the leftmost and rightmost elements that are out of order.
• The length of the shortest subarray is the difference between these indices.

Implementation:

int findUnsortedSubarray(vector<int>& nums) {
    int n = nums.size();
    int left = 0, right = n - 1;

    while (left < n - 1 && nums[left] <= nums[left + 1]) {
        ++left;
    }

    if (left == n - 1) {
        return 0;
    }

    while (right > 0 && nums[right] >= nums[right - 1]) {
        --right;
    }

    int minVal = *min_element(nums.begin() + left, nums.begin() + right + 1);
    int maxVal = *max_element(nums.begin() + left, nums.begin() + right + 1);

    while (left > 0 && nums[left - 1] > minVal) {
        --left;
    }
    while (right < n - 1 && nums[right + 1] < maxVal) {
        ++right;
    }

    return right - left + 1;
}

Reflection:
Today’s problems provided great practice with sliding windows and identifying subarrays that need sorting. The first problem on finding the smallest range covering elements from k sorted lists sharpened my sliding window technique, while the second problem on finding the length of the shortest unsorted subarray gave me a deep understanding of range-based operations and sorting-related algorithms. Both challenges enhanced my problem-solving skills significantly.

Looking forward to more!