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-arrayvector<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 codeint 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-arraydef 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 codea =[ 1, 4, 3, 2, 5 ]k = 4n = len(a)# Get the sub-arrayans = findSubarray(a, k, n)for it in ans: print(it,end=" ") # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing 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-arrayfunction 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 codevar a = [1, 4, 3, 2, 5];var k = 4;var n = a.length;// Get the sub-arrayvar 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
