Manoj Rao bio photo

Manoj Rao

Your Average Common Man

Email Twitter Github

The title of this post should describe what I imply here. I came across a class of puzzles which fit a mould of solution.

Note: This is only for contiguous subgroups not the same as interleaved subsequences.

std::vector<int> arr = {1, 1, 2, 3, 2, 0, 4, 0, 5, 0, 6};
std::vector<int> sub_ = {1, 2, 3}; // not {1, 2, 3, 4, 5, 6} which is non-contig

Find the Longest/Shortest Sliding Window:

This problem occurs in real life far more often than expected. All the way from network protocol implementation to pattern matching to generic book keeping tasks.

Basic Building Blocks:

The basic building blocks for solving such problems are that you need a left and a right iterator which form the window. The size of this window is determined by which direction the iterators move in.

Window Resizing:

For most cases, the input array (or a string) already dictates an in-built ordering (L -> R). As a convention, we extend the window by moving the right iterator and shrink it by moving the left.

Goal: Consume input only once, O(N)

By going over the input once, we guarantee that the worst case is O(N). However, this does require us to carefully manage the boundaries of the window.

Code Snippet:

Assume the problem is to find the longest window of increasing numbers in a given array (Common interview problem, perhaps).

// shown once here for clarity
struct max_sub {
    size_t max_len;
    std::pair <int, int> sub_idx;
    max_sub() : max_len(0) {}
};

using sub_arr_t = struct max_sub;

template <typename T>
auto longest_inc_sub(const std::vector<T>& arr) -> sub_arr_t {
    // init stack vars here ...

    auto update_global_max_ = [&max_] (int l, int r) {
        auto local_ = r - l + 1;
        if (local_ > max_.max_len) { max_.max_len = local_; max_.sub_idx = std::make_pair(l, r); }
    };

    while (r < arr.size() && (l <= r)) {
	    while (arr[l] < arr[r]) { r++; }
	    update_global_max_(l, r);
	    l++;
    }

    return max_;
}

// ... Caller

auto incr_subarr = longest_inc_sub(input_arr);

Core Logic:

The magic all happens in this bit of the code, which simply extends the window to the right if the condition is satisfied. If the condition check fails, then the left iterator is advanced (or the window is shrunk) for the new input to be consumed.

    while (r < arr.size() && (l <= r)) {
	    while (arr[l] < arr[r]) { r++; }
	    update_global_max_(l, r);
	    l++;
    }

Generic Code:

Now let’s try to make this code apply to a broader set of problems that require a sliding window run over the input. The code becomes:

    
template <typename T, typename Pred>
auto sliding_win_(const std::vector<T>& arr, Pred& p, MinMax& u) -> sub_arr_t {
    // init stack vars here

    while (r < arr.size() && (l <= r)) {
	    while (p(arr[l], arr[r])) { r++; }
	    u(max_, l, r);
	    l++;
    }

    return max_;
}

// ...
// Caller

sliding_win_(input_arr, 
        [=](const auto& l, const auto& r) -> bool { return (l < r); }, 
        [=](auto& book_keeper, const auto& l, const auto& r) -> bool {
			auto local_ = r - l + 1;
			book_keeper.update_min(l, r);
			// OR book_keeper.update_max(l, r);
		);

As you can see, the control for the logic now rests with the caller who can invoke this generic sliding window algorithm in a powerful, succinct manner.


Bring Your Own Cause

If you think any info here has remotely helped you consider dropping a penny for this cause, just click me . You can visit https://www.bbc.com/news/world-asia-india-52672764 Unfortunately, there are plenty of sad things happening all over the world, if you have a different cause or charity you'd rather support please do. And if you did make a donation, please drop a note to me (annotated) or leave a comment here (anonymous is OK!) and I will use that as motivation to write more useful content here.

If you like topics such as this then please consider subscribing to my podcast. I talk to some of the stalwarts in tech and ask them what their favorite productivity hacks are:

Available on iTunes Podcast

Visit Void Star Podcast’s page on iTunes Podcast Portal. Please Click ‘Subscribe’, leave a comment.

Get it iTunes