Click here to Skip to main content
16,021,112 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Given a set of arrays of size and an integer , you have to find the maximum integer for each and
every contiguous subarray of size for each of the given arrays.
Input Format
First line of input will contain the number of test cases T. For each test case, you will be given the size of
array N and the size of subarray to be used K. This will be followed by the elements of the array A .
Constraints
, where is the element in the array .
Output Format
For each of the contiguous subarrays of size of each array, you have to print the maximum integer.
Sample Input
i
2
5 2
3 4 6 3 4
7 4
3 4 5 8 1 4 10
Sample Output
4 6 6 4
8 8 8 10
Explanation
For the first case, the contiguous subarrays of size 2 are {3,4},{4,6},{6,3} and {3,4}. The 4 maximum
elements of subarray of size 2 are: 4 6 6 4.
For the second case,the contiguous subarrays of size 4 are {3,4,5,8},{4,5,8,1},{5,8,1,4} and {8,1,4,10}.
The 4 maximum element of subarray of size 4 are: 8 8 8 10.


I'm struggling with a question on hackerrank. I have implemented an algorithm which finds the maximum element in the windows and stores its index, then use this index of the maximum element in the previous window to find the maximum element in the next window only if the index of maximum element lies between the indexes of the next window. I've tried many test cases but i'm still unable to figure out the error in the code.

What I have tried:

C++
using namespace std;
#include<iostream>
#include<algorithm>
int m,idx,ct=0;
void maxinwindow(int arr[], int start, int end)
{
    /*If the index of the maximum element in the previous window
    is between the indexes of next windows then no need to compare elements
    that were in previous window */
    if(idx>=start)
    {
        if(arr[idx]>=arr[end])
        {
        	if(arr[idx]==arr[end])
			{
        		idx=end;	
			}
            //ct++;
            m=arr[idx];
        }
        else
        {
            //ct++;
            m=arr[end];
            idx=end;
        }
    }
    else
    {
        if(arr[start]>=arr[start+1])
        {
            //ct++;
            m=arr[start];
        }
        else
        {
            //ct++;
            m=arr[start+1];
        }
        for(int k=start+2;k<=end;k++)
        {
            //ct++;
            if(arr[k]>=m)
            {
                m=arr[k];
                idx=k;
            }
        }
    }
}
int main()
{
    int arr[100000];
    int q;
    cin>>q;
    for(int i=1,size,ws;i<=q;i++)
    {
        m=0;ct=0;
        cin>>size;  //Array size
        cin>>ws;   //Window Size
        //Entering The Elements In The Array
        for(int j=1;j<=size;j++)
        {
            cin>>arr[j];
        }
        //Boundary Condition i.e. Windows size is equal to 1
        if(ws==1)
        {
            for(int j=1;j<=size;j++)
            {
                cout<<arr[j]<<" ";
            }
        }
        else
        {
            for(int k=1;k<=ws;k++)
            {
                //ct++;
                if(arr[k]>=m)
                {
                    m=arr[k];
                    idx=k;
                }
            }
            //ct--;
            cout<<m<<" ";           
            for(int k=2,j;k<=(size-(ws-1));k++)
            {
                j=(k+(ws-1));
                maxinwindow(arr,k,j);
                cout<<m<<" ";
            }
            cout<<endl;
        }
    }
}
Posted
Updated 9-Jan-19 22:44pm
v3
Comments
CPallini 10-Jan-19 3:13am    
I suppose you should report the exact requirements, since Hacker Rank is not available to the few of us not willing to sign up.
Shantanu Dwivedi 10-Jan-19 3:21am    
yeah sure.
Patrice T 10-Jan-19 3:33am    
Adding your wrong results for the examples may help us to figure out how it is wrong.
CPallini 10-Jan-19 3:44am    
I see (thanks to Patrice) it is intended as an exercise on std::deque. Then why (the fresh Hell) don't you use std::deque?
Shantanu Dwivedi 10-Jan-19 3:46am    
i can but i want to know whats wrong is with this algorithm.

An easily spotted mistake in your code is going out-of-bounds on arr array:
Quote:
int arr[10000];
int q;
cin>>q;
for(int i=1,size,ws;i<=q;i++)
{
m=0;ct=0;
cin>>size; //Array size
cin>>ws; //Window Size
//Entering The Elements In The Array
for(int j=1;j<=size;j++)
{
cin>>arr[j]; //<-- here the code might wrongly access arr[10000]
}

when size = 10000 you are out-of-luck.
 
Share this answer
 
Comments
Shantanu Dwivedi 10-Jan-19 4:06am    
the limit is mentioned in the question.
Maciej Los 10-Jan-19 4:08am    
Take a look at bloded text ;)
CPallini 10-Jan-19 4:17am    
When you declare arr[10000], the available items are
arr[0], arr[1], ..., arr[9999]
It is C++, not Visual Basic.
Shantanu Dwivedi 10-Jan-19 4:45am    
the problem still persists.
CPallini 10-Jan-19 5:01am    
Then, there is another bug (or there are other bugs).
The most sensible approach I am able to see is:
(1) implement a (maybe deadly slow) bullet-proof algorithm, either using std::deque or not.
(2) generate large sets of random inputs and compare the two implementations results on such sets.
(3) enlighted by the mismatches, inspect the code to find out the bug(s).
Quote:
I've tried many test cases but i'm still unable to figure out the error in the code.

Your code do not behave the way you expect, or you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your code is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]

1.11 — Debugging your program (stepping and breakpoints) | Learn C++[^]

The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
 
Share this answer
 
Comments
Shantanu Dwivedi 10-Jan-19 3:48am    
i've tried to debug it using IDE for many test cases and they all work.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900