Mixing
Time complexity of removing elements
3
I have a sorted Array:
let mySortedArray = [1,1,5,6,8,8,9,25,25]
I want to remove any duplicates from this array in O(1) time and space complexity. First of all, is this even possible?
My solution is the following:
I convert the array to a set and any duplicates are just removed.
let mySet = new Set(myArray);
What would the time and space complexity of that be?
And if I were to convert the set back to an Array:
let myNewArr = Array.from(mySet);
What would the time and space complexity of the whole method then be?
Would this be the most optimal way of removing any duplicates of an array or would there be a better one?
javascript arrays duplicates set
asked Nov 21 '18 at 9:45
EDJEDJ
223114
add a comment |
3
I have a sorted Array:
let mySortedArray = [1,1,5,6,8,8,9,25,25]
I want to remove any duplicates from this array in O(1) time and space complexity. First of all, is this even possible?
My solution is the following:
I convert the array to a set and any duplicates are just removed.
let mySet = new Set(myArray);
What would the time and space complexity of that be?
And if I were to convert the set back to an Array:
let myNewArr = Array.from(mySet);
What would the time and space complexity of the whole method then be?
Would this be the most optimal way of removing any duplicates of an array or would there be a better one?
javascript arrays duplicates set
asked Nov 21 '18 at 9:45
EDJEDJ
223114
I don't believe this is possible inO(1), as in order to know if there are any other elements which are duplicated you would have to go through the entire array, looking at each element at least once. Thus, I believe your only going to be able to getO(N)for your time complexity. This also may provide further insight
– Nick Parsons
Nov 21 '18 at 9:53
I don't think O(1) is possible for this. Creating a Set from an array uses the iterator interface iirc, so the complexity is O(n) I think, since every element of the array still gets looped over to add it to the Set. Since the array is already sorted, there's probably some way to get a fraction of O(n), but you still have to check at least two elements since we don't know yet how many unique elements there are.
– Shilly
Nov 21 '18 at 9:56
Since I don't support Set() yet, I use the following general function, which is O(n) i think:const unique = () => { const seen = {}; return item => { const json = JSON.stringify( item ); return seen.hasOwnProperty( json ) ? false : ( seen[ json ] = true ); }; };and thenmySortedArray.filter( unique() );.
– Shilly
Nov 21 '18 at 9:57
There is some related info at this post:Remove duplicate values from JS array.
– prasad_
Nov 21 '18 at 10:33
Since you already have a sorted array I guess the following:[1,1,5,6,8,8,9,25,25].filter((item,index,all)=>all[index-1]!==item)will be best from the related post
– HMR
Nov 21 '18 at 13:18
add a comment |
3
3
3
I have a sorted Array:
let mySortedArray = [1,1,5,6,8,8,9,25,25]
I want to remove any duplicates from this array in O(1) time and space complexity. First of all, is this even possible?
My solution is the following:
I convert the array to a set and any duplicates are just removed.
let mySet = new Set(myArray);
What would the time and space complexity of that be?
And if I were to convert the set back to an Array:
let myNewArr = Array.from(mySet);
What would the time and space complexity of the whole method then be?
Would this be the most optimal way of removing any duplicates of an array or would there be a better one?
javascript arrays duplicates set
asked Nov 21 '18 at 9:45
EDJEDJ
223114
I have a sorted Array:
let mySortedArray = [1,1,5,6,8,8,9,25,25]
I want to remove any duplicates from this array in O(1) time and space complexity. First of all, is this even possible?
My solution is the following:
I convert the array to a set and any duplicates are just removed.
let mySet = new Set(myArray);
What would the time and space complexity of that be?
And if I were to convert the set back to an Array:
let myNewArr = Array.from(mySet);
What would the time and space complexity of the whole method then be?
Would this be the most optimal way of removing any duplicates of an array or would there be a better one?
javascript arrays duplicates set
javascript arrays duplicates set
asked Nov 21 '18 at 9:45
EDJEDJ
223114
asked Nov 21 '18 at 9:45
EDJEDJ
223114
asked Nov 21 '18 at 9:45
EDJEDJ
223114
asked Nov 21 '18 at 9:45
EDJEDJ
223114
asked Nov 21 '18 at 9:45
EDJEDJ
223114
223114
I don't believe this is possible inO(1), as in order to know if there are any other elements which are duplicated you would have to go through the entire array, looking at each element at least once. Thus, I believe your only going to be able to getO(N)for your time complexity. This also may provide further insight
– Nick Parsons
Nov 21 '18 at 9:53
I don't think O(1) is possible for this. Creating a Set from an array uses the iterator interface iirc, so the complexity is O(n) I think, since every element of the array still gets looped over to add it to the Set. Since the array is already sorted, there's probably some way to get a fraction of O(n), but you still have to check at least two elements since we don't know yet how many unique elements there are.
– Shilly
Nov 21 '18 at 9:56
Since I don't support Set() yet, I use the following general function, which is O(n) i think:const unique = () => { const seen = {}; return item => { const json = JSON.stringify( item ); return seen.hasOwnProperty( json ) ? false : ( seen[ json ] = true ); }; };and thenmySortedArray.filter( unique() );.
– Shilly
Nov 21 '18 at 9:57
There is some related info at this post:Remove duplicate values from JS array.
– prasad_
Nov 21 '18 at 10:33
Since you already have a sorted array I guess the following:[1,1,5,6,8,8,9,25,25].filter((item,index,all)=>all[index-1]!==item)will be best from the related post
– HMR
Nov 21 '18 at 13:18
add a comment |
I don't believe this is possible inO(1), as in order to know if there are any other elements which are duplicated you would have to go through the entire array, looking at each element at least once. Thus, I believe your only going to be able to getO(N)for your time complexity. This also may provide further insight
– Nick Parsons
Nov 21 '18 at 9:53
I don't think O(1) is possible for this. Creating a Set from an array uses the iterator interface iirc, so the complexity is O(n) I think, since every element of the array still gets looped over to add it to the Set. Since the array is already sorted, there's probably some way to get a fraction of O(n), but you still have to check at least two elements since we don't know yet how many unique elements there are.
– Shilly
Nov 21 '18 at 9:56
Since I don't support Set() yet, I use the following general function, which is O(n) i think:const unique = () => { const seen = {}; return item => { const json = JSON.stringify( item ); return seen.hasOwnProperty( json ) ? false : ( seen[ json ] = true ); }; };and thenmySortedArray.filter( unique() );.
– Shilly
Nov 21 '18 at 9:57
There is some related info at this post:Remove duplicate values from JS array.
– prasad_
Nov 21 '18 at 10:33
Since you already have a sorted array I guess the following:[1,1,5,6,8,8,9,25,25].filter((item,index,all)=>all[index-1]!==item)will be best from the related post
– HMR
Nov 21 '18 at 13:18
I don't believe this is possible in
O(1), as in order to know if there are any other elements which are duplicated you would have to go through the entire array, looking at each element at least once. Thus, I believe your only going to be able to get O(N) for your time complexity. This also may provide further insight– Nick Parsons
Nov 21 '18 at 9:53
I don't believe this is possible in
O(1), as in order to know if there are any other elements which are duplicated you would have to go through the entire array, looking at each element at least once. Thus, I believe your only going to be able to get O(N) for your time complexity. This also may provide further insight– Nick Parsons
Nov 21 '18 at 9:53
I don't think O(1) is possible for this. Creating a Set from an array uses the iterator interface iirc, so the complexity is O(n) I think, since every element of the array still gets looped over to add it to the Set. Since the array is already sorted, there's probably some way to get a fraction of O(n), but you still have to check at least two elements since we don't know yet how many unique elements there are.
– Shilly
Nov 21 '18 at 9:56
I don't think O(1) is possible for this. Creating a Set from an array uses the iterator interface iirc, so the complexity is O(n) I think, since every element of the array still gets looped over to add it to the Set. Since the array is already sorted, there's probably some way to get a fraction of O(n), but you still have to check at least two elements since we don't know yet how many unique elements there are.
– Shilly
Nov 21 '18 at 9:56
Since I don't support Set() yet, I use the following general function, which is O(n) i think:
const unique = () => { const seen = {}; return item => { const json = JSON.stringify( item ); return seen.hasOwnProperty( json ) ? false : ( seen[ json ] = true ); }; }; and then mySortedArray.filter( unique() );.– Shilly
Nov 21 '18 at 9:57
Since I don't support Set() yet, I use the following general function, which is O(n) i think:
const unique = () => { const seen = {}; return item => { const json = JSON.stringify( item ); return seen.hasOwnProperty( json ) ? false : ( seen[ json ] = true ); }; }; and then mySortedArray.filter( unique() );.– Shilly
Nov 21 '18 at 9:57
There is some related info at this post:Remove duplicate values from JS array.
– prasad_
Nov 21 '18 at 10:33
There is some related info at this post:Remove duplicate values from JS array.
– prasad_
Nov 21 '18 at 10:33
Since you already have a sorted array I guess the following:
[1,1,5,6,8,8,9,25,25].filter((item,index,all)=>all[index-1]!==item) will be best from the related post– HMR
Nov 21 '18 at 13:18
Since you already have a sorted array I guess the following:
[1,1,5,6,8,8,9,25,25].filter((item,index,all)=>all[index-1]!==item) will be best from the related post– HMR
Nov 21 '18 at 13:18
add a comment |
0
active
oldest
votes
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
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%2f53409211%2ftime-complexity-of-removing-elements%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
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%2f53409211%2ftime-complexity-of-removing-elements%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
I don't believe this is possible in
O(1), as in order to know if there are any other elements which are duplicated you would have to go through the entire array, looking at each element at least once. Thus, I believe your only going to be able to getO(N)for your time complexity. This also may provide further insight– Nick Parsons
Nov 21 '18 at 9:53
I don't think O(1) is possible for this. Creating a Set from an array uses the iterator interface iirc, so the complexity is O(n) I think, since every element of the array still gets looped over to add it to the Set. Since the array is already sorted, there's probably some way to get a fraction of O(n), but you still have to check at least two elements since we don't know yet how many unique elements there are.
– Shilly
Nov 21 '18 at 9:56
Since I don't support Set() yet, I use the following general function, which is O(n) i think:
const unique = () => { const seen = {}; return item => { const json = JSON.stringify( item ); return seen.hasOwnProperty( json ) ? false : ( seen[ json ] = true ); }; };and thenmySortedArray.filter( unique() );.– Shilly
Nov 21 '18 at 9:57
There is some related info at this post:Remove duplicate values from JS array.
– prasad_
Nov 21 '18 at 10:33
Since you already have a sorted array I guess the following:
[1,1,5,6,8,8,9,25,25].filter((item,index,all)=>all[index-1]!==item)will be best from the related post– HMR
Nov 21 '18 at 13:18