Hackerrank “Almost Equal” solution
up vote
1
down vote
favorite
I've spent the best part of a day on this question. It is marked as Expert which is way above my level but I gave it my best attempt. There are about fifteen submission test cases and my solution manages to satisfy the first four. However, from there on in it hits timeouts due to performance issues.
Hackerrank question
There doesn't seem to be much information or solutions for this question around, so I would appreciate if anyone had any suggestion on how I can improve the performance. Maybe I need to go back to the drawing board with my approach.
- N = number of elements in the array
- K = The height difference allowed
- H = Array of heights
- queries = 2D array of ranges within which you must find the number of matching pairs (i.e. how many fighters in this range meet the height requirements to fight each other)
My approach is to copy the subset (I know this is slow and would like to get around it somehow)and then run a quicksort over this new subset.
With this we can now quickly figure out what heights are within range of each other (i.e. if we get height = 1 and we know k = 2, then the maximum height he can fight against is going to be 3).
static int solve(int n, int k, int h, int queries) {
// N = no. heights
// K = Difference
// L & R = First and Last fighters
int results = new int[queries.length];
int count = 1;
int pairs = 0;
int l, r =0;
for(int j=0; j<queries.length; j++) {
l = queries[j][0];
r = queries[j][1];
int range = Arrays.copyOfRange(h, l, r+1);
int sortedSubset = sort(range);
for(int i=0; i<sortedSubset.length-1; i++) {
count = i+1;
while((count != sortedSubset.length) && sortedSubset[count] <= (sortedSubset[i]+k)) {
// While the current number is still in range of the number we are checking i.e. (number + k)
pairs++;
count++;
}
}
results[j] = pairs;
pairs = 0;
}
return results;
}
java performance algorithm sorting quick-sort
New contributor
add a comment |
up vote
1
down vote
favorite
I've spent the best part of a day on this question. It is marked as Expert which is way above my level but I gave it my best attempt. There are about fifteen submission test cases and my solution manages to satisfy the first four. However, from there on in it hits timeouts due to performance issues.
Hackerrank question
There doesn't seem to be much information or solutions for this question around, so I would appreciate if anyone had any suggestion on how I can improve the performance. Maybe I need to go back to the drawing board with my approach.
- N = number of elements in the array
- K = The height difference allowed
- H = Array of heights
- queries = 2D array of ranges within which you must find the number of matching pairs (i.e. how many fighters in this range meet the height requirements to fight each other)
My approach is to copy the subset (I know this is slow and would like to get around it somehow)and then run a quicksort over this new subset.
With this we can now quickly figure out what heights are within range of each other (i.e. if we get height = 1 and we know k = 2, then the maximum height he can fight against is going to be 3).
static int solve(int n, int k, int h, int queries) {
// N = no. heights
// K = Difference
// L & R = First and Last fighters
int results = new int[queries.length];
int count = 1;
int pairs = 0;
int l, r =0;
for(int j=0; j<queries.length; j++) {
l = queries[j][0];
r = queries[j][1];
int range = Arrays.copyOfRange(h, l, r+1);
int sortedSubset = sort(range);
for(int i=0; i<sortedSubset.length-1; i++) {
count = i+1;
while((count != sortedSubset.length) && sortedSubset[count] <= (sortedSubset[i]+k)) {
// While the current number is still in range of the number we are checking i.e. (number + k)
pairs++;
count++;
}
}
results[j] = pairs;
pairs = 0;
}
return results;
}
java performance algorithm sorting quick-sort
New contributor
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I've spent the best part of a day on this question. It is marked as Expert which is way above my level but I gave it my best attempt. There are about fifteen submission test cases and my solution manages to satisfy the first four. However, from there on in it hits timeouts due to performance issues.
Hackerrank question
There doesn't seem to be much information or solutions for this question around, so I would appreciate if anyone had any suggestion on how I can improve the performance. Maybe I need to go back to the drawing board with my approach.
- N = number of elements in the array
- K = The height difference allowed
- H = Array of heights
- queries = 2D array of ranges within which you must find the number of matching pairs (i.e. how many fighters in this range meet the height requirements to fight each other)
My approach is to copy the subset (I know this is slow and would like to get around it somehow)and then run a quicksort over this new subset.
With this we can now quickly figure out what heights are within range of each other (i.e. if we get height = 1 and we know k = 2, then the maximum height he can fight against is going to be 3).
static int solve(int n, int k, int h, int queries) {
// N = no. heights
// K = Difference
// L & R = First and Last fighters
int results = new int[queries.length];
int count = 1;
int pairs = 0;
int l, r =0;
for(int j=0; j<queries.length; j++) {
l = queries[j][0];
r = queries[j][1];
int range = Arrays.copyOfRange(h, l, r+1);
int sortedSubset = sort(range);
for(int i=0; i<sortedSubset.length-1; i++) {
count = i+1;
while((count != sortedSubset.length) && sortedSubset[count] <= (sortedSubset[i]+k)) {
// While the current number is still in range of the number we are checking i.e. (number + k)
pairs++;
count++;
}
}
results[j] = pairs;
pairs = 0;
}
return results;
}
java performance algorithm sorting quick-sort
New contributor
I've spent the best part of a day on this question. It is marked as Expert which is way above my level but I gave it my best attempt. There are about fifteen submission test cases and my solution manages to satisfy the first four. However, from there on in it hits timeouts due to performance issues.
Hackerrank question
There doesn't seem to be much information or solutions for this question around, so I would appreciate if anyone had any suggestion on how I can improve the performance. Maybe I need to go back to the drawing board with my approach.
- N = number of elements in the array
- K = The height difference allowed
- H = Array of heights
- queries = 2D array of ranges within which you must find the number of matching pairs (i.e. how many fighters in this range meet the height requirements to fight each other)
My approach is to copy the subset (I know this is slow and would like to get around it somehow)and then run a quicksort over this new subset.
With this we can now quickly figure out what heights are within range of each other (i.e. if we get height = 1 and we know k = 2, then the maximum height he can fight against is going to be 3).
static int solve(int n, int k, int h, int queries) {
// N = no. heights
// K = Difference
// L & R = First and Last fighters
int results = new int[queries.length];
int count = 1;
int pairs = 0;
int l, r =0;
for(int j=0; j<queries.length; j++) {
l = queries[j][0];
r = queries[j][1];
int range = Arrays.copyOfRange(h, l, r+1);
int sortedSubset = sort(range);
for(int i=0; i<sortedSubset.length-1; i++) {
count = i+1;
while((count != sortedSubset.length) && sortedSubset[count] <= (sortedSubset[i]+k)) {
// While the current number is still in range of the number we are checking i.e. (number + k)
pairs++;
count++;
}
}
results[j] = pairs;
pairs = 0;
}
return results;
}
java performance algorithm sorting quick-sort
java performance algorithm sorting quick-sort
New contributor
New contributor
edited 5 mins ago
Jamal♦
30.2k11115226
30.2k11115226
New contributor
asked 2 hours ago
Mark Peter Mc Adam
62
62
New contributor
New contributor
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
I suggest you do the following:
- Sort the entire heights array once.
- Finds all the matching pairs for the full array (i.e.
l=0; r=h.length-1;
). - For each matching pair you find, loop over the
queries
array, and add it to the counts of all the subsets that contain both fighters. For example, if the pairh[2]
,h[5]
is matching, incrementresults[j]
for allj
such thatqueries[j][0] <=2
and5 <= queries[j][1]
.
I believe running a single sort instead of queries.length
sorts will improve the performance.
The only downside of this algorithm is that if all the queries cover a small subset of the full heights array, the algorithm will do a lot of unnecessary work (finding matching pairs for indices that we'll never need to count).
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
I suggest you do the following:
- Sort the entire heights array once.
- Finds all the matching pairs for the full array (i.e.
l=0; r=h.length-1;
). - For each matching pair you find, loop over the
queries
array, and add it to the counts of all the subsets that contain both fighters. For example, if the pairh[2]
,h[5]
is matching, incrementresults[j]
for allj
such thatqueries[j][0] <=2
and5 <= queries[j][1]
.
I believe running a single sort instead of queries.length
sorts will improve the performance.
The only downside of this algorithm is that if all the queries cover a small subset of the full heights array, the algorithm will do a lot of unnecessary work (finding matching pairs for indices that we'll never need to count).
add a comment |
up vote
0
down vote
I suggest you do the following:
- Sort the entire heights array once.
- Finds all the matching pairs for the full array (i.e.
l=0; r=h.length-1;
). - For each matching pair you find, loop over the
queries
array, and add it to the counts of all the subsets that contain both fighters. For example, if the pairh[2]
,h[5]
is matching, incrementresults[j]
for allj
such thatqueries[j][0] <=2
and5 <= queries[j][1]
.
I believe running a single sort instead of queries.length
sorts will improve the performance.
The only downside of this algorithm is that if all the queries cover a small subset of the full heights array, the algorithm will do a lot of unnecessary work (finding matching pairs for indices that we'll never need to count).
add a comment |
up vote
0
down vote
up vote
0
down vote
I suggest you do the following:
- Sort the entire heights array once.
- Finds all the matching pairs for the full array (i.e.
l=0; r=h.length-1;
). - For each matching pair you find, loop over the
queries
array, and add it to the counts of all the subsets that contain both fighters. For example, if the pairh[2]
,h[5]
is matching, incrementresults[j]
for allj
such thatqueries[j][0] <=2
and5 <= queries[j][1]
.
I believe running a single sort instead of queries.length
sorts will improve the performance.
The only downside of this algorithm is that if all the queries cover a small subset of the full heights array, the algorithm will do a lot of unnecessary work (finding matching pairs for indices that we'll never need to count).
I suggest you do the following:
- Sort the entire heights array once.
- Finds all the matching pairs for the full array (i.e.
l=0; r=h.length-1;
). - For each matching pair you find, loop over the
queries
array, and add it to the counts of all the subsets that contain both fighters. For example, if the pairh[2]
,h[5]
is matching, incrementresults[j]
for allj
such thatqueries[j][0] <=2
and5 <= queries[j][1]
.
I believe running a single sort instead of queries.length
sorts will improve the performance.
The only downside of this algorithm is that if all the queries cover a small subset of the full heights array, the algorithm will do a lot of unnecessary work (finding matching pairs for indices that we'll never need to count).
answered 1 hour ago
Eran
311312
311312
add a comment |
add a comment |
Mark Peter Mc Adam is a new contributor. Be nice, and check out our Code of Conduct.
Mark Peter Mc Adam is a new contributor. Be nice, and check out our Code of Conduct.
Mark Peter Mc Adam is a new contributor. Be nice, and check out our Code of Conduct.
Mark Peter Mc Adam is a new contributor. Be nice, and check out our Code of Conduct.
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.
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%2fcodereview.stackexchange.com%2fquestions%2f209489%2fhackerrank-almost-equal-solution%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