• 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

Reliance Jio Software Developer Interview Experience

Find min element in Sorted Rotated Array (Without Duplicates)

CodeChef Code SGARDEN

Right view of Binary tree

FizzBuzz Solution C C++

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

Test Cases for Round Function

SAP Off Campus Hiring_ March 2015 Computer Skills

Python String and numbers

Adobe Interview Questions 8 month Exp

Subset Sum Problem Dynamic programming

SAP Hiring Off-Campus General Aptitude

Max Sum in circularly situated Values

Printing Longest Common Subsequence

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

Sort an array according to the order defined by another array

LeetCode: Container With Most Water

Binary Tree in Java

Maximum path sum between two leaves

Calculate price of parking from parking start end time prices

Sort Stack in place

Daughter’s Age VeryGood Puzzle

Coin Collection Dynamic Programming

Practo Hiring Experience

Binary Tree Isomorphic to each other

Regular Expression Matching

Find Pythagorean Triplets in an array in O(N)

Find the smallest window in a string containing all characters of another string

Circular Linked List

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

Copyright © 2023 · Genesis Framework · WordPress · Log in