• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Maximum of all subarrays of size k

December 20, 2014 by Dhaval Dave

Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3
SubArray : [1,2,3] , [2,3,1], [3,1,4] …..
Output :
3 3 4 5 5 5 6
Method 1)

– Keep Front pointer and endpointer to decide Window of subarray.
– For first SubArray find Max number and print.
– Keep Index of Max.
–  increament pointers for Front & End. Check whether new element is larger than max or not.
– if larger mark it as max.
– if new SubArray crosses index of Max, Find new Max and Store index of it.

#include <stdio.h>
#include <iostream>
using namespace std;
void printKMax(int arr[], int n, int k)
{
    int fr=0, max=arr[0],maxindex;
    
  for(int i=0;i<k;i++){
  if(arr[i]>=max) {max=arr[i]; maxindex=i;}
  }
  //cout<<“initialmax=”<<max<<” maxindex=”<<maxindex<<“n”;
  cout<<max<<” “;
  fr=1;
    for (int i=k; i<n; i++)
    {
   
if(maxindex>=fr && maxindex<=i){
        if (arr[i] >= max){ 
        max = arr[i];
        maxindex=i;
        }
}
else if(maxindex<fr){
max=arr[fr];
for(int j=fr;j<=i;j++){
if(arr[j]>=max){max=arr[j];maxindex=j;}
}
}
//cout<<“[“<<arr[fr]<<“-“<<arr[i]<<“] max=”<<max<<“n”;
cout<<max<<” “;
fr++;
    }
}

int main()
{
    //int arr[] = {12, 1, 78, 90, 57, 89, 56};
    int arr[]={1,2,3,4,5,6,7,8,9,10,11};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    printKMax(arr, n, k);
    return 0;
}
Working Code at  : http://ideone.com/78MRE3

Similar Articles

Filed Under: Flipkart Interview Questions, Microsoft Interview Questions, problem Tagged With: Array

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Implement LRU Cache

Common Ancestor in a Binary Tree or Binary Search Tree

Flipkart Set 1 On Campus with Answers

Maximum sum contiguous subarray of an Array

Amazon Interview On-Campus For Internship – 1

How Radix sort works

Advanced SQL Injection

Word Break Problem

Fibonacci Hashing & Fastest Hashtable

The greedy coins game Dynamic Programming

Test Cases for Round Function

Given a float number convert it into the string WITHOUT using any inbuilt Function

Find Nearest Minimum number in left side in O(n)

Count Possible Decodings of a given Digit Sequence

Python List

Print Power Set of a Set

Cisco Hiring Event 21st – 22nd Feb 2015

Leetcode: Edit Distance

Regular Expression Matching

System Design: Designing a LLD for Hotel Booking

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

Find and print longest consecutive number sequence in a given sequence in O(n)

Get K Max and Delete K Max in stream of incoming integers

Diagonal Traversal of Binary Tree

Find the number ABCD such that when multipled by 4 gives DCBA.

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Print vertical sum of all the axis in the given binary tree

Max Sum in circularly situated Values

Number of Islands BFS/DFS

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

Copyright © 2025 · Genesis Framework · WordPress · Log in