Greatest contiguous sub-array of size K

0 0 4 minutes read

Given an array arr[] of integers and an integer K, the task is to find the greatest contiguous sub-array of size K. Sub-array X is said to be greater than sub-array Y if the first non-matching element in both the sub-arrays has a greater value in X than in Y.

Examples:

Input: arr[] = {1, 4, 3, 2, 5}, K = 4
Output: 4 3 2 5
Two subarrays are {1, 4, 3, 2} and {4, 3, 2, 5}.
Hence, the greater one is {4, 3, 2, 5}

Input: arr[] = {1, 9, 2, 7, 9, 3}, K = 3
Output: 9 2 7

Approach: Generate all the sub-arrays of size K and store them in any Data-Structure. Sort all the sub-arrays, and the answer will be the last sub-array in the sorted Data-structure. In C++, we can use a vector of vectors to store sub-arrays of size K.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the sub-array
vector<int> findSubarray(int a[], int k, int n)
{
 
    // Data-structure to store all
    // the sub-arrays of size K
    vector<vector<int> > vec;
 
    // Iterate to find all the sub-arrays
    for (int i = 0; i < n - k + 1; i++) {
        vector<int> temp;
 
        // Store the sub-array elements in the array
        for (int j = i; j < i + k; j++) {
            temp.push_back(a[j]);
        }
 
        // Push the vector in the container
        vec.push_back(temp);
    }
 
    // Sort the vector of elements
    sort(vec.begin(), vec.end());
 
    // The last sub-array in the sorted order
    // will be the answer
    return vec[vec.size() - 1];
}
 
// Driver code
int main()
{
    int a[] = { 1, 4, 3, 2, 5 };
    int k = 4;
    int n = sizeof(a) / sizeof(a[0]);
 
    // Get the sub-array
    vector<int> ans = findSubarray(a, k, n);
 
    for (auto it : ans)
        cout << it << " ";
}

Java

// Java implementation of the approach 
import java.io.*;
import java.util.*;
 
class GFG{
     
// Function that returns the sub-array 
static ArrayList<Integer> findSubarray(int a[], 
                                       int k, int n)
{
     
    // Data-structure to store all 
    // the sub-arrays of size K 
    ArrayList<
    ArrayList<Integer>> vec = new ArrayList<
                                  ArrayList<Integer>>();
                                   
    // Iterate to find all the sub-arrays 
    for(int i = 0; i < n - k + 1; i++)
    {
        ArrayList<Integer> temp = new ArrayList<Integer>();
         
        // Store the sub-array elements in the array 
        for(int j = i; j < i + k; j++)
        {
            temp.add(a[j]);
        }
         
        // Push the vector in the container 
        vec.add(temp);
    }
     
     // Sort the vector of elements
    Collections.sort(vec, new Comparator<ArrayList<Integer>>()
    {    
        @Override
        public int compare(ArrayList<Integer> o1, 
                           ArrayList<Integer> o2)
        {
            return o1.get(0).compareTo(o2.get(0));
        }               
    });
     
    // The last sub-array in the sorted order 
    // will be the answer 
    return vec.get(vec.size() - 1);
}
 
// Driver code 
public static void main(String[] args) 
{
    int a[] = { 1, 4, 3, 2, 5 }; 
    int k = 4; 
    int n = a.length;
     
    // Get the sub-array
    ArrayList<Integer> ans = findSubarray(a, k, n);
     
    for(int it: ans)
    {
        System.out.print(it + " ");
    }
}
}
 
// This code is contributed by avanitrachhadiya2155

Python3

# Python3 implementation of the approach
 
# Function that returns the sub-array
def findSubarray(a, k, n):
 
    # Data-structure to store all
    # the sub-arrays of size K
    vec=[]
 
    # Iterate to find all the sub-arrays
    for i in range(n-k+1):
        temp=[]
 
        # Store the sub-array elements in the array
        for j in range(i,i+k):
            temp.append(a[j])
 
        # Push the vector in the container
        vec.append(temp)
 
    # Sort the vector of elements
    vec=sorted(vec)
 
    # The last sub-array in the sorted order
    # will be the answer
    return vec[len(vec) - 1]
 
# Driver code
 
a =[ 1, 4, 3, 2, 5 ]
k = 4
n = len(a)
 
# Get the sub-array
ans = findSubarray(a, k, n)
 
for it in ans:
    print(it,end=" ")
     
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
using System.Linq;
 
public class GFG
{
 
  // Function that returns the sub-array 
  static List<int> findSubarray(int[] a, int k, int n)
  {
    // Data-structure to store all 
    // the sub-arrays of size K 
    List<List<int>> vec = new List<List<int>>();
 
    // Iterate to find all the sub-arrays 
    for(int i = 0; i < n - k + 1; i++)
    {
      List<int> temp = new List<int>();
 
      // Store the sub-array elements in the array 
      for(int j = i; j < i + k; j++)
      {
        temp.Add(a[j]);
      }
 
      // Push the vector in the container 
      vec.Add(temp);
    }
 
    // Sort the vector of elements
    vec.OrderBy( l => l[0]);
 
    // The last sub-array in the sorted order 
    // will be the answer 
    return vec[vec.Count - 1];
  }
 
  // Driver code 
  static public void Main (){
    int[] a = { 1, 4, 3, 2, 5 }; 
    int k = 4; 
    int n = a.Length;
 
    // Get the sub-array
    List<int> ans = findSubarray(a, k, n);
    foreach(int it in ans)
    {
      Console.Write(it + " ");
    }
  }
}
 
// This code is contributed by rag2127

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function that returns the sub-array
function findSubarray(a, k, n)
{
 
    // Data-structure to store all
    // the sub-arrays of size K
    var vec = [];
 
    // Iterate to find all the sub-arrays
    for (var i = 0; i < n - k + 1; i++) {
        var temp = [];
 
        // Store the sub-array elements in the array
        for (var j = i; j < i + k; j++) {
            temp.push(a[j]);
        }
 
        // Push the vector in the container
        vec.push(temp);
    }
 
    // Sort the vector of elements
    vec.sort()
 
    // The last sub-array in the sorted order
    // will be the answer
    return vec[vec.length - 1];
}
 
// Driver code
var a = [1, 4, 3, 2, 5];
var k = 4;
var n = a.length;
 
// Get the sub-array
var ans = findSubarray(a, k, n);
ans.forEach(it => {
    document.write(it+ " ")
});
 
// This code is contributed by noob2000.
</script>

Output:

4 3 2 5

Time Complexity: O(n*n), as nested loops are used
Auxiliary Space: O(n), as extra space of size n is used to make vector and vector of vectors.

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 zambiatek!