{"id":27607,"date":"2018-04-04T19:34:08","date_gmt":"2018-04-04T14:04:08","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27607"},"modified":"2018-04-04T19:34:08","modified_gmt":"2018-04-04T14:04:08","slug":"java-programming-count-distinct-elements-every-window-size-k","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-count-distinct-elements-every-window-size-k\/","title":{"rendered":"Java Programming – Count distinct elements in every window of size k"},"content":{"rendered":"

Given an array of size n and an integer k, return the of count of distinct numbers in all windows of size k.<\/span><\/p>\n

Example:<\/p>\n

Input:  arr[] = {1, 2, 1, 3, 4, 2, 3};\r\n            k = 4\r\nOutput:\r\n3\r\n4\r\n4\r\n3\r\n\r\nExplanation:\r\nFirst window is {1, 2, 1, 3}, count of distinct numbers is 3\r\nSecond window is {2, 1, 3, 4} count of distinct numbers is 4\r\nThird window is {1, 3, 4, 2} count of distinct numbers is 4\r\nFourth window is {3, 4, 2, 3} count of distinct numbers is 3<\/pre>\n
An Efficient Solution<\/strong> is to use the count of previous window, while sliding the window. The idea is to create a hash map that stores elements of current widow. When we slide the window, we remove an element from hash and add an element. We also keep track of distinct elements. Below is algorithm.<\/p>\n
1) Create an empty hash map. Let hash map be hM<\/p>\n
2) Initialize distinct element count \u2018dist_count\u2019 as 0.<\/p>\n
3) Traverse through first window and insert elements of first window to hM. The elements are used as key and their counts as value in hM. Also keep updating \u2018dist_count\u2019<\/p>\n
4) Print \u2018dist_count\u2019 for first window.<\/p>\n
3) Traverse through remaining array (or other windows).
\n\u2026.a) Remove the first element of previous window.
\n\u2026\u2026.If the removed element appeared only once
\n\u2026\u2026\u2026\u2026..remove it from hM and do \u201cdist_count\u2013\u201d
\n\u2026\u2026.Else (appeared multiple times in hM)
\n\u2026\u2026\u2026\u2026..decrement its count in hM<\/p>\n
\u2026.a) Add the current element (last element of new window)
\n\u2026\u2026.If the added element is not present in hM
\n\u2026\u2026\u2026\u2026..add it to hM and do \u201cdist_count++\u201d
\n\u2026\u2026.Else (the added element appeared multiple times)
\n\u2026\u2026\u2026\u2026..increment its count in hM<\/p>\n
Below is implementation of above approach.<\/p>\n
 
 Java Program<\/span> <\/div> 
\/\/ An efficient Java program to count distinct elements in\/\/ every window of size kimport java.util.HashMap; class CountDistinctWindow{    static void countDistinct(int arr[], int k)    {        \/\/ Creates an empty hashMap hM        HashMap<Integer, Integer> hM =                      new HashMap<Integer, Integer>();         \/\/ initialize distinct element  count for        \/\/ current window        int dist_count = 0;         \/\/ Traverse the first window and store count        \/\/ of every element in hash map        for (int i = 0; i < k; i++)        {            if (hM.get(arr[i]) == null)            {                hM.put(arr[i], 1);                dist_count++;            }            else            {               int count = hM.get(arr[i]);               hM.put(arr[i], count+1);            }        }         \/\/ Print count of first window        System.out.println(dist_count);         \/\/ Traverse through the remaining array        for (int i = k; i < arr.length; i++)        {             \/\/ Remove first element of previous window            \/\/ If there was only one occurrence, then            \/\/ reduce distinct count.            if (hM.get(arr[i-k]) == 1)            {                hM.remove(arr[i-k]);                dist_count--;            }            else \/\/ reduce count of the removed element            {               int count = hM.get(arr[i-k]);               hM.put(arr[i-k], count-1);            }             \/\/ Add new element of current window            \/\/ If this element appears first time,            \/\/ increment distinct element count            if (hM.get(arr[i]) == null)            {                hM.put(arr[i], 1);                dist_count++;            }            else \/\/ Increment distinct element count            {               int count = hM.get(arr[i]);               hM.put(arr[i], count+1);            }            \/\/ Print count of current window            System.out.println(dist_count);        }    }     \/\/ Driver method    public static void main(String arg[])    {        int arr[] =  {1, 2, 1, 3, 4, 2, 3};        int k = 4;        countDistinct(arr, k);    }}<\/code><\/pre> <\/div>\n
Output:<\/p>\n
3\r\n4\r\n4\r\n3<\/pre>\n
Time complexity of the above solution is O(n).<\/p>\n","protected":false},"excerpt":{"rendered":"
An Efficient Solution is to use the count of previous window, while sliding the window. The idea is to create a hash map that stores elements.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80128],"tags":[81829,81823,81822,81831,81830,81827,81820,81824,81825,81826,81828,81821,81819,81818,52264],"class_list":["post-27607","post","type-post","status-publish","format-standard","hentry","category-hashing","tag-moving-average-method","tag-rank-in-sql","tag-rank-over-partition-by","tag-slider-window","tag-sliding-window","tag-sliding-window-algorithm","tag-sliding-window-in-networking","tag-sliding-window-protocol-program-in-c","tag-sliding-window-protocol-program-in-java","tag-sql-analytic-functions","tag-tcp","tag-tcp-frame-format","tag-tcp-packet-format","tag-tcp-sliding-window","tag-windows-partition"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27607","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\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27607"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27607\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27607"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27607"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27607"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}