Searching for shortest slice in an array with all unique values, how to do this in optimal way?












0















I have an array that contains N elements, which values are in 0 <= value < N range and can be discontinuous. For this array I need to find a slice which will contain all unique values and at the same time it will be the shortest slice that will meet the above criterion.



An example, for array {1, 2, 1, 2, 1, 4, 3, 4, 8, 1, 8} with 5 unique values {1, 2, 3, 4, 8} we are talking about slice {2, 1, 4, 3, 4, 8} with length 6.



Is there an optimal way to do this? As for now I've naive implementation that has far too high complexity (nested loops). I've tried to come up with an idea for an algorithm to do this in an optimal way but sadly to no avail. As for now I've tried to come up with something that will make use of occurrences for each unique value when looping through array, but still my mind is not clear enough. Any ideas are welcome, this problem is troubling me for a long time. :) Thank you in advance.



Best regards










share|improve this question























  • The simplest solution appears to involve two passes through the list. One from the left and one from the right. Alternatively, one to prepare the list of unique elements and one to find the slice.

    – Kapil
    Nov 21 '18 at 7:22











  • I think you want slice with all possible values.

    – MBo
    Nov 21 '18 at 8:02
















0















I have an array that contains N elements, which values are in 0 <= value < N range and can be discontinuous. For this array I need to find a slice which will contain all unique values and at the same time it will be the shortest slice that will meet the above criterion.



An example, for array {1, 2, 1, 2, 1, 4, 3, 4, 8, 1, 8} with 5 unique values {1, 2, 3, 4, 8} we are talking about slice {2, 1, 4, 3, 4, 8} with length 6.



Is there an optimal way to do this? As for now I've naive implementation that has far too high complexity (nested loops). I've tried to come up with an idea for an algorithm to do this in an optimal way but sadly to no avail. As for now I've tried to come up with something that will make use of occurrences for each unique value when looping through array, but still my mind is not clear enough. Any ideas are welcome, this problem is troubling me for a long time. :) Thank you in advance.



Best regards










share|improve this question























  • The simplest solution appears to involve two passes through the list. One from the left and one from the right. Alternatively, one to prepare the list of unique elements and one to find the slice.

    – Kapil
    Nov 21 '18 at 7:22











  • I think you want slice with all possible values.

    – MBo
    Nov 21 '18 at 8:02














0












0








0








I have an array that contains N elements, which values are in 0 <= value < N range and can be discontinuous. For this array I need to find a slice which will contain all unique values and at the same time it will be the shortest slice that will meet the above criterion.



An example, for array {1, 2, 1, 2, 1, 4, 3, 4, 8, 1, 8} with 5 unique values {1, 2, 3, 4, 8} we are talking about slice {2, 1, 4, 3, 4, 8} with length 6.



Is there an optimal way to do this? As for now I've naive implementation that has far too high complexity (nested loops). I've tried to come up with an idea for an algorithm to do this in an optimal way but sadly to no avail. As for now I've tried to come up with something that will make use of occurrences for each unique value when looping through array, but still my mind is not clear enough. Any ideas are welcome, this problem is troubling me for a long time. :) Thank you in advance.



Best regards










share|improve this question














I have an array that contains N elements, which values are in 0 <= value < N range and can be discontinuous. For this array I need to find a slice which will contain all unique values and at the same time it will be the shortest slice that will meet the above criterion.



An example, for array {1, 2, 1, 2, 1, 4, 3, 4, 8, 1, 8} with 5 unique values {1, 2, 3, 4, 8} we are talking about slice {2, 1, 4, 3, 4, 8} with length 6.



Is there an optimal way to do this? As for now I've naive implementation that has far too high complexity (nested loops). I've tried to come up with an idea for an algorithm to do this in an optimal way but sadly to no avail. As for now I've tried to come up with something that will make use of occurrences for each unique value when looping through array, but still my mind is not clear enough. Any ideas are welcome, this problem is troubling me for a long time. :) Thank you in advance.



Best regards







arrays algorithm unique slice shortest






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked Nov 21 '18 at 5:16









cafebabe_tcafebabe_t

207




207













  • The simplest solution appears to involve two passes through the list. One from the left and one from the right. Alternatively, one to prepare the list of unique elements and one to find the slice.

    – Kapil
    Nov 21 '18 at 7:22











  • I think you want slice with all possible values.

    – MBo
    Nov 21 '18 at 8:02



















  • The simplest solution appears to involve two passes through the list. One from the left and one from the right. Alternatively, one to prepare the list of unique elements and one to find the slice.

    – Kapil
    Nov 21 '18 at 7:22











  • I think you want slice with all possible values.

    – MBo
    Nov 21 '18 at 8:02

















The simplest solution appears to involve two passes through the list. One from the left and one from the right. Alternatively, one to prepare the list of unique elements and one to find the slice.

– Kapil
Nov 21 '18 at 7:22





The simplest solution appears to involve two passes through the list. One from the left and one from the right. Alternatively, one to prepare the list of unique elements and one to find the slice.

– Kapil
Nov 21 '18 at 7:22













I think you want slice with all possible values.

– MBo
Nov 21 '18 at 8:02





I think you want slice with all possible values.

– MBo
Nov 21 '18 at 8:02












1 Answer
1






active

oldest

votes


















0














The first run collects possible values and creates a map with pairs (value; counter = 0). Let Nis map size



For the second run prepare two indexes - left and right, and ActiveCnt.



Move right, updating map counters. When you update zero counter, increment ActiveCnt. When ActiveCnt becomes equal to N, stop.



Now move left, decrementing map counters. When some counter becomes zero, get difference between right and left, compare it with current MinLength, then decrement ActiveCnt. Continue with right index and so on.






share|improve this answer























    Your Answer






    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "1"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53405651%2fsearching-for-shortest-slice-in-an-array-with-all-unique-values-how-to-do-this%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    0














    The first run collects possible values and creates a map with pairs (value; counter = 0). Let Nis map size



    For the second run prepare two indexes - left and right, and ActiveCnt.



    Move right, updating map counters. When you update zero counter, increment ActiveCnt. When ActiveCnt becomes equal to N, stop.



    Now move left, decrementing map counters. When some counter becomes zero, get difference between right and left, compare it with current MinLength, then decrement ActiveCnt. Continue with right index and so on.






    share|improve this answer




























      0














      The first run collects possible values and creates a map with pairs (value; counter = 0). Let Nis map size



      For the second run prepare two indexes - left and right, and ActiveCnt.



      Move right, updating map counters. When you update zero counter, increment ActiveCnt. When ActiveCnt becomes equal to N, stop.



      Now move left, decrementing map counters. When some counter becomes zero, get difference between right and left, compare it with current MinLength, then decrement ActiveCnt. Continue with right index and so on.






      share|improve this answer


























        0












        0








        0







        The first run collects possible values and creates a map with pairs (value; counter = 0). Let Nis map size



        For the second run prepare two indexes - left and right, and ActiveCnt.



        Move right, updating map counters. When you update zero counter, increment ActiveCnt. When ActiveCnt becomes equal to N, stop.



        Now move left, decrementing map counters. When some counter becomes zero, get difference between right and left, compare it with current MinLength, then decrement ActiveCnt. Continue with right index and so on.






        share|improve this answer













        The first run collects possible values and creates a map with pairs (value; counter = 0). Let Nis map size



        For the second run prepare two indexes - left and right, and ActiveCnt.



        Move right, updating map counters. When you update zero counter, increment ActiveCnt. When ActiveCnt becomes equal to N, stop.



        Now move left, decrementing map counters. When some counter becomes zero, get difference between right and left, compare it with current MinLength, then decrement ActiveCnt. Continue with right index and so on.







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Nov 21 '18 at 8:02









        MBoMBo

        49k23050




        49k23050
































            draft saved

            draft discarded




















































            Thanks for contributing an answer to Stack Overflow!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53405651%2fsearching-for-shortest-slice-in-an-array-with-all-unique-values-how-to-do-this%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            這個網誌中的熱門文章

            Xamarin.form Move up view when keyboard appear

            Post-Redirect-Get with Spring WebFlux and Thymeleaf

            Anylogic : not able to use stopDelay()