Shreyash Rai

Today I learned

Sliding Window

c++neetcodedsa

Sliding Window#

So now we are onto sliding windows. This is a twin brother to two pointers, except here we do not have two pointers converging from either side, but two pointers (l and r)moving in the same direction. If our target is reaching, we expand the window by r++ and if our target is not being reached, we l++, reducing the size of the window. We end the condition if l or r reach the end of the list or l becomes larger than r.

1. Best Time to Buy And Sell Stock#

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int l=0; int r = 0;
        int maxProf = 0;
        while (l <= r && r < n && l < n-1){
            int profit = prices[r] - prices[l];
            maxProf = max(maxProf, profit);
            if (profit >= 0){
                r++;
            }
            else {
                l++;
            }
        }
        return maxProf;
    }
};

Problems I faced#

  • New approach means I had no idea how to look at the problem. I saw the O(n2) brute force solution of checking each pair, but I did not attempt it. I looked through how sliding window approaches work, and thought I should code something like achieving a target, expanding and retracting the window as we go. And et voila, I managed it.

What else can be done?#

  • So this works yeah, but we waste passes trying to check for negative profits. We could add a break when profit is negative. But that’s minimal.
  • In this problem we only expanded right IF we were already having a good profit, and if we didn’t we move the left forward. A more efficient method would be doing r++ regardless, every time. We only update l based on profit.
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int l=0; int r = 1;
        int maxProf = 0;
        while (r < n){
            if (prices[l] < prices[r]){
                int profit = prices[r] - prices[l];
                maxProf = max(maxProf, profit);
            }
            else {
                l=r;
            }
            r++;
        }
        return maxProf;
    }
};
  • We did l=r because l tracks the minimum price so far.

Can we get faster#

  • Yes. A dynamic programming approach solves this too.
  • Just remember the minimum price seen so far. Store the max profit as you go in the array.
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minimum = INT_MAX;
        int maxProf = 0;
        for (int x : prices){
            minimum = min(minimum, x);
            maxProf = max(maxProf, x - minimum);
        }
        return maxProf;
    }
};
  • Ah a simple solution.

2. Longest Substring Without Repeating Characters#

I wrote:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) return 0;
        int low=0;
        int high=0;
        int n = s.size();
        if (n == 1) return 1;
        unordered_map<char, int> running;
        int longest = 0;
        while (high != n){
            if (running[s[high]] == 0) {
                running[s[high]] = 1;
                longest = max(high-low+1, longest);
                high++;
            }
            else {
                running[s[low]]=0;
                low++;
            }
        }
        return longest;
    }
};

Late at night at 3 am, I started doing this problem. I thought of a simple sliding window approach where I would use low and high and increase high if favorable condition and increase low if not favorable condition. Store the maximum gap between low and high and return it at the end.

Some cool thing I did was I used running[s[high]] == 0 directly which creates s[high] as 0 in the hash-map, setting the existence of s[high] to false directly. I originally had a .find() there but the other condition where I set running[s[low]] = 0 was failing and I didn’t know how to delete elements from hash-maps. It’s done by .erase().

Problems I faced#

  • Before eating my time away in handling these stupid edge cases, I should have realized that my loops only work with more than 2 elements. This means, the edge cases exist of one or zero elements as well. And for strings, we have to always remember empty ones.
  • Had to change the while loop from while (low != n-1 && high!= n-1) to (high != n) after a lot of thinking.
  • The edge cases of empty strings troubled me a lot. I didn’t know how to handle s =" " which is a space character.

Can this be improved? I doubt it but let’s see.#

In terms of time complexity, no. My solution is O(n) because low and high visits each element once, each. (It’s 2n lol but we call it O(n) anyways).

We can improve it by:

  • Removing the early-skips because our while loop handles those already. I added them while testing edge case when my while loop was both while (low != n-1 && high!= n-1) and that was troubling me. After changing it to (high != n) the code worked and I hit submit.
  • When we hit a high that is a duplicate from current running elements (i.e. after low) we increase low one by one, which wastes steps. Instead of storing true and false values inside running, we can store the last seen index. When high becomes a duplicate, we can close the gap between duplicate and low directly.
  • Arrays are usually faster than hash-maps (for small sizes), and for our ASCII constraint, we could go for a 128 size array.
  • In this version, we need last seen >= low because a duplicate could exist that’s behind low. And since we never removed the duplicate from hash-maps (like we did originally), we need this.
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> last(128, -1); //last seen index of 128 possible ascii char
        int low=0; int longest=0;
        for (int high=0; high < (int)s.size(); ++high){
            unsigned char c = s[high];
            if (last[c] >= low) low = last[c]+1; //skip elements
            last[c] = high; //reset last seen
            longest = max(longest, high-low+1);
        }
        return longest;
    }
};