Remove all occurrences of an element from an array, in place
$begingroup$
I solved this problem:
Given an array
numsand a valueval, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
How can I improve its execution time and also, if there is any better way of doing it?
public int removeElement(int numbers, int value) {
int index = 0;
for(; index < numbers.length; index++) {
if(numbers[index] == value) {
boolean otherNumberPresent = false;
int j = index + 1;
for(; j < numbers.length; j++ ){
if(numbers[j] != value) {
otherNumberPresent = true;
break;
}
}
if(otherNumberPresent) {
int temp = numbers[j];
numbers[j] = numbers[index];
numbers[index] = temp;
} else {
return index;
}
}
}
return index;
}
java performance programming-challenge
edited Dec 24 '18 at 20:14
200_success
130k16153419
asked Dec 24 '18 at 19:46
Karan KhannaKaran Khanna
1656
$endgroup$
add a comment |
$begingroup$
I solved this problem:
Given an array
numsand a valueval, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
How can I improve its execution time and also, if there is any better way of doing it?
public int removeElement(int numbers, int value) {
int index = 0;
for(; index < numbers.length; index++) {
if(numbers[index] == value) {
boolean otherNumberPresent = false;
int j = index + 1;
for(; j < numbers.length; j++ ){
if(numbers[j] != value) {
otherNumberPresent = true;
break;
}
}
if(otherNumberPresent) {
int temp = numbers[j];
numbers[j] = numbers[index];
numbers[index] = temp;
} else {
return index;
}
}
}
return index;
}
java performance programming-challenge
edited Dec 24 '18 at 20:14
200_success
130k16153419
asked Dec 24 '18 at 19:46
Karan KhannaKaran Khanna
1656
$endgroup$
add a comment |
$begingroup$
I solved this problem:
Given an array
numsand a valueval, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
How can I improve its execution time and also, if there is any better way of doing it?
public int removeElement(int numbers, int value) {
int index = 0;
for(; index < numbers.length; index++) {
if(numbers[index] == value) {
boolean otherNumberPresent = false;
int j = index + 1;
for(; j < numbers.length; j++ ){
if(numbers[j] != value) {
otherNumberPresent = true;
break;
}
}
if(otherNumberPresent) {
int temp = numbers[j];
numbers[j] = numbers[index];
numbers[index] = temp;
} else {
return index;
}
}
}
return index;
}
java performance programming-challenge
edited Dec 24 '18 at 20:14
200_success
130k16153419
asked Dec 24 '18 at 19:46
Karan KhannaKaran Khanna
1656
$endgroup$
I solved this problem:
Given an array
numsand a valueval, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
How can I improve its execution time and also, if there is any better way of doing it?
public int removeElement(int numbers, int value) {
int index = 0;
for(; index < numbers.length; index++) {
if(numbers[index] == value) {
boolean otherNumberPresent = false;
int j = index + 1;
for(; j < numbers.length; j++ ){
if(numbers[j] != value) {
otherNumberPresent = true;
break;
}
}
if(otherNumberPresent) {
int temp = numbers[j];
numbers[j] = numbers[index];
numbers[index] = temp;
} else {
return index;
}
}
}
return index;
}
java performance programming-challenge
java performance programming-challenge
edited Dec 24 '18 at 20:14
200_success
130k16153419
asked Dec 24 '18 at 19:46
Karan KhannaKaran Khanna
1656
edited Dec 24 '18 at 20:14
200_success
130k16153419
asked Dec 24 '18 at 19:46
Karan KhannaKaran Khanna
1656
edited Dec 24 '18 at 20:14
200_success
130k16153419
edited Dec 24 '18 at 20:14
200_success
130k16153419
edited Dec 24 '18 at 20:14
200_success
130k16153419
130k16153419
asked Dec 24 '18 at 19:46
Karan KhannaKaran Khanna
1656
asked Dec 24 '18 at 19:46
Karan KhannaKaran Khanna
1656
asked Dec 24 '18 at 19:46
Karan KhannaKaran Khanna
1656
1656
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
A much simpler solution is to have an "input pointer" i and an "output pointer" o.
public int removeElement(int numbers, int value) {
int o = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] != value) {
numbers[o++] = numbers[i];
}
}
return o;
}
answered Dec 24 '18 at 20:13
200_success200_success
130k16153419
$endgroup$
add a comment |
$begingroup$
The fundamental issue with your code is that it has two loops in it. As a rule of thumb, that suggests it is a quadratic algorithm: if you double the size of the input, the runtime could be four times worse.
In practice that should (depending on the input profile) happen rarely, so long as the array doesn't have the first half full of the target number and the second full of other stuff. But even with a more random distribution, this will be slower than needed because it keeps dumping the values to remove back into the bit of the array it is about to search!
The answer by 200_success works well enough, but also has a higher than necessary cost because it writes something in almost every step of the loop.
There is another solution, hinted at in the question with the order doesn't matter clause: when you need to delete something, move the replacement from the end. Because the end is discarded anyway, you don't even need to swap out the old value with the one you want to delete.
Although it is dangerous to predict without profiling, that will probably prove a more efficient approach. The heuristic is that most steps in the loop will just be a read and equality comparison before moving on to the next step. (This should also be friendly to a bunch of low level details such as the cache coherence and branch predictor, but that is very detailed and really needs profiling.)
answered Dec 25 '18 at 0:07
JosiahJosiah
3,742428
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
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: "196"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fcodereview.stackexchange.com%2fquestions%2f210282%2fremove-all-occurrences-of-an-element-from-an-array-in-place%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
A much simpler solution is to have an "input pointer" i and an "output pointer" o.
public int removeElement(int numbers, int value) {
int o = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] != value) {
numbers[o++] = numbers[i];
}
}
return o;
}
answered Dec 24 '18 at 20:13
200_success200_success
130k16153419
$endgroup$
add a comment |
$begingroup$
A much simpler solution is to have an "input pointer" i and an "output pointer" o.
public int removeElement(int numbers, int value) {
int o = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] != value) {
numbers[o++] = numbers[i];
}
}
return o;
}
answered Dec 24 '18 at 20:13
200_success200_success
130k16153419
$endgroup$
add a comment |
$begingroup$
A much simpler solution is to have an "input pointer" i and an "output pointer" o.
public int removeElement(int numbers, int value) {
int o = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] != value) {
numbers[o++] = numbers[i];
}
}
return o;
}
answered Dec 24 '18 at 20:13
200_success200_success
130k16153419
$endgroup$
A much simpler solution is to have an "input pointer" i and an "output pointer" o.
public int removeElement(int numbers, int value) {
int o = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] != value) {
numbers[o++] = numbers[i];
}
}
return o;
}
answered Dec 24 '18 at 20:13
200_success200_success
130k16153419
answered Dec 24 '18 at 20:13
200_success200_success
130k16153419
answered Dec 24 '18 at 20:13
200_success200_success
130k16153419
answered Dec 24 '18 at 20:13
200_success200_success
130k16153419
130k16153419
add a comment |
add a comment |
$begingroup$
The fundamental issue with your code is that it has two loops in it. As a rule of thumb, that suggests it is a quadratic algorithm: if you double the size of the input, the runtime could be four times worse.
In practice that should (depending on the input profile) happen rarely, so long as the array doesn't have the first half full of the target number and the second full of other stuff. But even with a more random distribution, this will be slower than needed because it keeps dumping the values to remove back into the bit of the array it is about to search!
The answer by 200_success works well enough, but also has a higher than necessary cost because it writes something in almost every step of the loop.
There is another solution, hinted at in the question with the order doesn't matter clause: when you need to delete something, move the replacement from the end. Because the end is discarded anyway, you don't even need to swap out the old value with the one you want to delete.
Although it is dangerous to predict without profiling, that will probably prove a more efficient approach. The heuristic is that most steps in the loop will just be a read and equality comparison before moving on to the next step. (This should also be friendly to a bunch of low level details such as the cache coherence and branch predictor, but that is very detailed and really needs profiling.)
answered Dec 25 '18 at 0:07
JosiahJosiah
3,742428
$endgroup$
add a comment |
$begingroup$
The fundamental issue with your code is that it has two loops in it. As a rule of thumb, that suggests it is a quadratic algorithm: if you double the size of the input, the runtime could be four times worse.
In practice that should (depending on the input profile) happen rarely, so long as the array doesn't have the first half full of the target number and the second full of other stuff. But even with a more random distribution, this will be slower than needed because it keeps dumping the values to remove back into the bit of the array it is about to search!
The answer by 200_success works well enough, but also has a higher than necessary cost because it writes something in almost every step of the loop.
There is another solution, hinted at in the question with the order doesn't matter clause: when you need to delete something, move the replacement from the end. Because the end is discarded anyway, you don't even need to swap out the old value with the one you want to delete.
Although it is dangerous to predict without profiling, that will probably prove a more efficient approach. The heuristic is that most steps in the loop will just be a read and equality comparison before moving on to the next step. (This should also be friendly to a bunch of low level details such as the cache coherence and branch predictor, but that is very detailed and really needs profiling.)
answered Dec 25 '18 at 0:07
JosiahJosiah
3,742428
$endgroup$
add a comment |
$begingroup$
The fundamental issue with your code is that it has two loops in it. As a rule of thumb, that suggests it is a quadratic algorithm: if you double the size of the input, the runtime could be four times worse.
In practice that should (depending on the input profile) happen rarely, so long as the array doesn't have the first half full of the target number and the second full of other stuff. But even with a more random distribution, this will be slower than needed because it keeps dumping the values to remove back into the bit of the array it is about to search!
The answer by 200_success works well enough, but also has a higher than necessary cost because it writes something in almost every step of the loop.
There is another solution, hinted at in the question with the order doesn't matter clause: when you need to delete something, move the replacement from the end. Because the end is discarded anyway, you don't even need to swap out the old value with the one you want to delete.
Although it is dangerous to predict without profiling, that will probably prove a more efficient approach. The heuristic is that most steps in the loop will just be a read and equality comparison before moving on to the next step. (This should also be friendly to a bunch of low level details such as the cache coherence and branch predictor, but that is very detailed and really needs profiling.)
answered Dec 25 '18 at 0:07
JosiahJosiah
3,742428
$endgroup$
The fundamental issue with your code is that it has two loops in it. As a rule of thumb, that suggests it is a quadratic algorithm: if you double the size of the input, the runtime could be four times worse.
In practice that should (depending on the input profile) happen rarely, so long as the array doesn't have the first half full of the target number and the second full of other stuff. But even with a more random distribution, this will be slower than needed because it keeps dumping the values to remove back into the bit of the array it is about to search!
The answer by 200_success works well enough, but also has a higher than necessary cost because it writes something in almost every step of the loop.
There is another solution, hinted at in the question with the order doesn't matter clause: when you need to delete something, move the replacement from the end. Because the end is discarded anyway, you don't even need to swap out the old value with the one you want to delete.
Although it is dangerous to predict without profiling, that will probably prove a more efficient approach. The heuristic is that most steps in the loop will just be a read and equality comparison before moving on to the next step. (This should also be friendly to a bunch of low level details such as the cache coherence and branch predictor, but that is very detailed and really needs profiling.)
answered Dec 25 '18 at 0:07
JosiahJosiah
3,742428
answered Dec 25 '18 at 0:07
JosiahJosiah
3,742428
answered Dec 25 '18 at 0:07
JosiahJosiah
3,742428
answered Dec 25 '18 at 0:07
JosiahJosiah
3,742428
3,742428
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fcodereview.stackexchange.com%2fquestions%2f210282%2fremove-all-occurrences-of-an-element-from-an-array-in-place%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
