ARRAYSUB - subarrays
Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
Input
the number n denoting number of elements in the array then after a new line we have the numbers of the array and then k in a new line
n < 10^6
k < 10^5
1 <= k <= n
and each element of the array is between 0 and 10^6
(Edited: In fact, n <= 10^5)
Output
print the output array
Example
Input: 9 1 2 3 1 4 5 2 3 6 3 Output: 3 3 4 5 5 5 6
hide comments
|
sohelr360:
2024-05-20 18:13:56
You can solve it using monotonic queue in O(n). |
|
tobiasveiga:
2023-12-10 13:04:12
n <= 10^5 did not work for me. My solution only got accepted when I used n < 10^6 |
|
uditmehra_827:
2023-10-19 04:39:53
do anyone have an approach without using set, multiset, i mean not using advantages of ds like multiset..?
|
|
mostafaasey25:
2022-06-26 11:07:58
my solution i hope its help : )
|
|
manoj0606:
2022-03-21 13:22:04
Simple solution using policy based ds in c++ :)
|
|
yasser1110:
2021-07-23 16:03:48
Really interesting problem. Learned tons from it. Solved it using c++ map. Because its implemented as a red black tree, we have O(logn) inserts, lookups and deletes. |
|
h4ck3rsh4d0w:
2021-06-23 15:52:24
AC in one go (used Max heap) |
|
nitin_20:
2021-05-09 03:48:18
Max of every k element |
|
kimg:
2021-02-10 16:45:56
Simple brutefoce works.
|
|
deerawat:
2021-01-03 10:19:56
Brute force works! |
| Added by: | priyamehtanit |
| Date: | 2012-02-09 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | own |
RSS