{"id":27393,"date":"2018-02-02T21:12:47","date_gmt":"2018-02-02T15:42:47","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27393"},"modified":"2018-02-02T21:12:47","modified_gmt":"2018-02-02T15:42:47","slug":"cc-programming-maximum-of-all-subarrays-of-size-k","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/cc-programming-maximum-of-all-subarrays-of-size-k\/","title":{"rendered":"C\/C++ Programming-Maximum of all sub arrays of size k"},"content":{"rendered":"

Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.<\/span><\/p>\n

Examples:<\/p>\n

Input :
\narr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
\nk = 3
\nOutput :
\n3 3 4 5 5 5 6<\/p>\n

Input :
\narr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}
\nk = 4
\nOutput :
\n10 10 10 15 15 90 90<\/p>\n

\u00a0Method 1 (Simple)<\/strong>
\nRun two loops. In the outer loop, take all subarrays of size k. In the inner loop, get the maximum of the current subarray<\/div>\n
<\/div>\n
C Programming<\/strong><\/div>\n
\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%20%0Avoid%20printKMax(int%20arr%5B%5D%2C%20int%20n%2C%20int%20k)%0A%7B%0A%20%20%20%20int%20j%2C%20max%3B%0A%20%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%3D%20n-k%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20max%20%3D%20arr%5Bi%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20for%20(j%20%3D%201%3B%20j%20%3C%20k%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bi%2Bj%5D%20%3E%20max)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20max%20%3D%20arr%5Bi%2Bj%5D%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20max)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%20%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B1%2C%202%2C%203%2C%204%2C%205%2C%206%2C%207%2C%208%2C%209%2C%2010%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20int%20k%20%3D%203%3B%0A%20%20%20%20printKMax(arr%2C%20n%2C%20k)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Time Complexity: The outer loop runs n-k+1 times and the inner loop runs k times for every iteration of outer loop. So time complexity is O((n-k+1)*k) which can also be written as O(nk).<\/p>\n[ad type=\u201dbanner\u201d]\n

Method 2 (Use Self-Balancing BST)<\/strong>
\n1) Pick first k elements and create a Self-Balancing Binary Search Tree (BST) of size k.
\n2) Run a loop for i = 0 to n \u2013 k
\na) Get the maximum element from the BST, and print it.
\nb) Search for arr[i] in the BST and delete it from the BST.
\nc) Insert arr[i+k] into the BST.<\/p>\n

Time Complexity: Time Complexity of step 1 is O(kLogk). Time Complexity of steps 2(a), 2(b) and 2(c) is O(Logk). Since steps 2(a), 2(b) and 2(c) are in a loop that runs n-k+1 times, time complexity of the complete algorithm is O(kLogk + (n-k+1)*Logk) which can also be written as O(nLogk).<\/p>\n[ad type=\u201dbanner\u201d]\n

Method 3 (A O(n) method: use Dequeue)<\/strong>
\nWe create a Dequeue<\/a>, Qi <\/em>of capacity k, that stores only useful elements of current window of k elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain Qi <\/em>to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi <\/em>is the largest and element at rear of Qi <\/em>is the smallest of current window.<\/p>\n[ad type=\u201dbanner\u201d]\n

Following is C++ implementation of this method.<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%23include%20%3Ciostream%3E%0A%23include%20%3Cdeque%3E%0A%20%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20Dequeue%20(Double%20ended%20queue)%20based%20method%20for%20printing%20maixmum%20element%20of%0A%2F%2F%20all%20subarrays%20of%20size%20k%0Avoid%20printKMax(int%20arr%5B%5D%2C%20int%20n%2C%20int%20k)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20Double%20Ended%20Queue%2C%20Qi%20that%20will%20store%20indexes%20of%20array%20elements%0A%20%20%20%20%2F%2F%20The%20queue%20will%20store%20indexes%20of%20useful%20elements%20in%20every%20window%20and%20it%20will%0A%20%20%20%20%2F%2F%20maintain%20decreasing%20order%20of%20values%20from%20front%20to%20rear%20in%20Qi%2C%20i.e.%2C%20%0A%20%20%20%20%2F%2F%20arr%5BQi.front%5B%5D%5D%20to%20arr%5BQi.rear()%5D%20are%20sorted%20in%20decreasing%20order%0A%20%20%20%20std%3A%3Adeque%3Cint%3E%20%20Qi(k)%3B%0A%20%0A%20%20%20%20%2F*%20Process%20first%20k%20(or%20first%20window)%20elements%20of%20array%20*%2F%0A%20%20%20%20int%20i%3B%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20k%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20For%20very%20element%2C%20the%20previous%20smaller%20elements%20are%20useless%20so%0A%20%20%20%20%20%20%20%20%2F%2F%20remove%20them%20from%20Qi%0A%20%20%20%20%20%20%20%20while%20(%20(!Qi.empty())%20%26%26%20arr%5Bi%5D%20%3E%3D%20arr%5BQi.back()%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20Qi.pop_back()%3B%20%20%2F%2F%20Remove%20from%20rear%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Add%20new%20element%20at%20rear%20of%20queue%0A%20%20%20%20%20%20%20%20Qi.push_back(i)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Process%20rest%20of%20the%20elements%2C%20i.e.%2C%20from%20arr%5Bk%5D%20to%20arr%5Bn-1%5D%0A%20%20%20%20for%20(%20%3B%20i%20%3C%20n%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20The%20element%20at%20the%20front%20of%20the%20queue%20is%20the%20largest%20element%20of%0A%20%20%20%20%20%20%20%20%2F%2F%20previous%20window%2C%20so%20print%20it%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20arr%5BQi.front()%5D%20%3C%3C%20%22%20%22%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Remove%20the%20elements%20which%20are%20out%20of%20this%20window%0A%20%20%20%20%20%20%20%20while%20(%20(!Qi.empty())%20%26%26%20Qi.front()%20%3C%3D%20i%20-%20k)%0A%20%20%20%20%20%20%20%20%20%20%20%20Qi.pop_front()%3B%20%20%2F%2F%20Remove%20from%20front%20of%20queue%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Remove%20all%20elements%20smaller%20than%20the%20currently%0A%20%20%20%20%20%20%20%20%2F%2F%20being%20added%20element%20(remove%20useless%20elements)%0A%20%20%20%20%20%20%20%20while%20(%20(!Qi.empty())%20%26%26%20arr%5Bi%5D%20%3E%3D%20arr%5BQi.back()%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20Qi.pop_back()%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%2F%2F%20Add%20current%20element%20at%20the%20rear%20of%20Qi%0A%20%20%20%20%20%20%20%20Qi.push_back(i)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Print%20the%20maximum%20element%20of%20last%20window%0A%20%20%20%20cout%20%3C%3C%20arr%5BQi.front()%5D%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B12%2C%201%2C%2078%2C%2090%2C%2057%2C%2089%2C%2056%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20int%20k%20%3D%203%3B%0A%20%20%20%20printKMax(arr%2C%20n%2C%20k)%3B%0A%20%20%20%20return%200%3B%0A%7D%0A\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Output:<\/p>\n

78 90 90 90 89<\/pre>\n
Time Complexity: O(n). It seems more than O(n) at first look. If we take a closer look, we can observe that every element of array is added and removed at most once. So there are total 2n operations.
\nAuxiliary Space: O(k)<\/p>\n[ad type=\u201dbanner\u201d]\n
<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
C\/C++ Programming Maximum of all sub arrays of size k Given an array and an integer k, find the maximum for each and every contiguous sub array of size k.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69866,1,73012,80124],"tags":[81630,81623,81626,83872,83874,83873,81625,83875],"class_list":["post-27393","post","type-post","status-publish","format-standard","hentry","category-c-programming","category-coding","category-data-structures","category-queue","tag-find-maximum-of-minimum-for-every-window-size-in-a-given-array","tag-maximum-of-all-subarrays-of-size-k-java","tag-maximum-sum-of-all-subarrays-of-size-k","tag-reverse-array-in-groups","tag-sliding-window-maximum","tag-sliding-window-maximum-maximum-of-all-subarrays-of-size-k","tag-sliding-window-maximum-java","tag-sliding-window-maximum-python"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27393","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27393"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27393\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27393"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27393"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27393"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}