Searching for shortest slice in an array with all unique values, how to do this in optimal way?
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
asked Nov 21 at 5:16
cafebabe_t
206
add a comment |
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
asked Nov 21 at 5:16
cafebabe_t
206
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 at 7:22
I think you want slice with all possible values.
– MBo
Nov 21 at 8:02
add a comment |
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
asked Nov 21 at 5:16
cafebabe_t
206
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
arrays algorithm unique slice shortest
asked Nov 21 at 5:16
cafebabe_t
206
asked Nov 21 at 5:16
cafebabe_t
206
asked Nov 21 at 5:16
cafebabe_t
206
asked Nov 21 at 5:16
cafebabe_t
206
asked Nov 21 at 5:16
cafebabe_t
206
206
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 at 7:22
I think you want slice with all possible values.
– MBo
Nov 21 at 8:02
add a comment |
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 at 7:22
I think you want slice with all possible values.
– MBo
Nov 21 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 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 at 7:22
I think you want slice with all possible values.
– MBo
Nov 21 at 8:02
I think you want slice with all possible values.
– MBo
Nov 21 at 8:02
add a comment |
1 Answer
1
active
oldest
votes
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.
answered Nov 21 at 8:02
MBo
47k22848
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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.
answered Nov 21 at 8:02
MBo
47k22848
add a comment |
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.
answered Nov 21 at 8:02
MBo
47k22848
add a comment |
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.
answered Nov 21 at 8:02
MBo
47k22848
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.
answered Nov 21 at 8:02
MBo
47k22848
answered Nov 21 at 8:02
MBo
47k22848
answered Nov 21 at 8:02
MBo
47k22848
answered Nov 21 at 8:02
MBo
47k22848
47k22848
add a comment |
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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 at 7:22
I think you want slice with all possible values.
– MBo
Nov 21 at 8:02