Largest Consecutive Subarray - C++ Solution

1. Introduction

The "Largest Consecutive Subarray" problem is a complex array manipulation challenge, focusing on finding a contiguous subarray formed by consecutive integers. This problem tests the ability to understand and implement algorithms that can efficiently search for sequences within an array.

Problem

Given an integer array, the task is to find the largest contiguous subarray that is formed by consecutive integers and contains all distinct values. In cases where multiple such subarrays of maximum length exist, the solution can return any one of them.

2. Solution Steps

1. Iterate through each element of the array and consider it as the starting point of a subarray.

2. For each starting point, find the range of consecutive numbers using a set to check for duplicates and track the maximum range.

3. The largest range gives the largest consecutive subarray.

4. Ensure that the elements in the considered range are consecutive.

3. Code Program

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

// Function to check if elements are consecutive
bool areConsecutive(vector<int>& arr, int i, int j) {
    unordered_set<int> s;
    for (int k = i; k <= j; k++) {
        // If duplicate is found, return false
        if (s.find(arr[k]) != s.end()) {
            return false;
        }
        s.insert(arr[k]);
    }

    // Check if elements are consecutive
    return *max_element(s.begin(), s.end()) - *min_element(s.begin(), s.end()) == j - i;
}

// Function to find the largest subarray of consecutive integers
vector<int> findLargestConsecutiveSubarray(vector<int>& arr) {
    int start = 0, end = 0;

    for (int i = 0; i < arr.size(); i++) {
        for (int j = i; j < arr.size(); j++) {
            if (areConsecutive(arr, i, j) && j - i > end - start) {
                start = i;
                end = j;
            }
        }
    }

    return vector<int>(arr.begin() + start, arr.begin() + end + 1);
}

int main() {
    vector<int> arr = {2, 0, 2, 1, 4, 3, 1, 0};
    vector<int> result = findLargestConsecutiveSubarray(arr);

    // Print the result
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

0 2 1 4 3

Explanation:

The function findLargestConsecutiveSubarray iterates over all possible subarrays and checks if the elements are consecutive and distinct using a set. It maintains the range of the largest subarray found that satisfies these conditions. 

The areConsecutive function is used to verify if the elements in a given range are consecutive and unique. 

This approach ensures that the largest consecutive subarray is found, considering all distinct values.