Given an array arr[] of size N, the task is to print the longest increasing subarray such that elements in the subarray are consecutive integers.
Examples:
Input: arr[] = {1, 9, 3, 4, 20, 2}
Output: {3, 4}
Explanation: The subarray {3, 4} is the longest subarray of consecutive elementsInput: arr[] = {36, 41, 56, 32, 33, 34, 35, 43, 32, 42}
Output: {32, 33, 34, 35}
Explanation: The subarray {32, 33, 34, 35} is the longest subarray of consecutive elements
Approach: The idea is to run a loop and keep a count and max (both initially zero). Follow the steps mentioned below:
- Run a loop from start to end
- If the current element is not equal to the (previous element+1) then set the count to 1, and update the window’s start and endpoints
- Else increase the count
- Finally, print the elements of the window
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to return the longest// consecutive subarrayvoid findLongestConseqSubarr(vector<int>& v){ int ans = 0, count = 0, start = 0, end = 0, x, y; // Find the maximum length // by traversing the array for (int i = 0; i < v.size(); i++) { // Check if the current element // is equal to previous element + 1 if (i > 0 && v[i] == v[i - 1] + 1) { count++; end = i; } // Reset the count else { start = i; count = 1; } // Update the maximum if (ans < count) { ans = count; x = start; y = end; } } for (int i = x; i <= y; i++) cout << v[i] << ", ";}// Driver Codeint main(){ vector<int> arr = { 1, 9, 3, 4, 20, 2 }; findLongestConseqSubarr(arr); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG {// Function to return the longest// consecutive subarraystatic void findLongestConseqSubarr(int arr[ ]){ int ans = 0, count = 0, start = 0, end = 0, x = 0, y = 0; // Find the maximum length // by traversing the array for (int i = 0; i < arr.length; i++) { // Check if the current element // is equal to previous element + 1 if (i > 0 && arr[i] == arr[i - 1] + 1) { count++; end = i; } // Reset the count else { start = i; count = 1; } // Update the maximum if (ans < count) { ans = count; x = start; y = end; } } for (int i = x; i <= y; i++) System.out.print(arr[i] + ", ");} public static void main (String[] args) { int arr[ ] = { 1, 9, 3, 4, 20, 2 }; findLongestConseqSubarr(arr); }}// This code is contributed by hrithikgarg03188 |
Python3
# Python program for the above approach# Function to return the longest# consecutive subarraydef findLongestConseqSubarr(v): ans = 0 count = 0 start = 0 end = 0 # Find the maximum length # by traversing the array for i in range(0, len(v)): # Check if the current element # is equal to previous element + 1 if (i > 0 and v[i] == v[i - 1] + 1): count = count + 1 end = i # Reset the count else: start = i count = 1 # Update the maximum if (ans < count): ans = count x = start y = end for i in range(x, y + 1): print(v[i], end = ", ")# Driver Codearr = [1, 9, 3, 4, 20, 2]findLongestConseqSubarr(arr)# This code is contributed by Taranpreet |
C#
// C# program for the above approachusing System;class GFG{ // Function to return the longest // consecutive subarray static void findLongestConseqSubarr(int[] arr) { int ans = 0, count = 0, start = 0, end = 0, x = 0, y = 0; // Find the maximum length // by traversing the array for (int i = 0; i < arr.Length; i++) { // Check if the current element // is equal to previous element + 1 if (i > 0 && arr[i] == arr[i - 1] + 1) { count++; end = i; } // Reset the count else { start = i; count = 1; } // Update the maximum if (ans < count) { ans = count; x = start; y = end; } } for (int i = x; i <= y; i++) Console.Write(arr[i] + ", "); } // Driver code public static void Main() { int[] arr = { 1, 9, 3, 4, 20, 2 }; findLongestConseqSubarr(arr); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script>// Javascript program for the above approach// Function to return the longest// consecutive subarrayfunction findLongestConseqSubarr(v){ let ans = 0, count = 0, start = 0, end = 0, x, y; // Find the maximum length // by traversing the array for (let i = 0; i < v.length; i++) { // Check if the current element // is equal to previous element + 1 if (i > 0 && v[i] == v[i - 1] + 1) { count++; end = i; } // Reset the count else { start = i; count = 1; } // Update the maximum if (ans < count) { ans = count; x = start; y = end; } } for (let i = x; i <= y; i++) document.write(v[i] + ", ");}// Driver Codelet arr = [ 1, 9, 3, 4, 20, 2 ]findLongestConseqSubarr(arr);// This code is contributed by gfgking.</script> |
Output
3, 4,
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
