Skip to content

Instantly share code, notes, and snippets.

@deedee47
Last active April 27, 2021 10:24
Show Gist options
  • Save deedee47/52eeee29bcab624a26967b2227f2e403 to your computer and use it in GitHub Desktop.
Save deedee47/52eeee29bcab624a26967b2227f2e403 to your computer and use it in GitHub Desktop.
Return an array of indexes to indicate the first and last occurrence of a value in an unsorted array
public int[] getBoundaryIndexesOfVal(int[] nums, int val){
if(nums == null) return new int[] {-1, -1};
if (nums.length == 0) return new int[] {-1, -1};
int startIndex = 0;
int endIndex = nums.length - 1;
//keep count of elements before and after the specified value
int preValCount = 0;
int postValCount = 0;
while(startIndex <= endIndex){ //if there's only one occurrence, start and end index will be the same
if(startIndex == endIndex){
if(nums[startIndex] < val) preValCount++;
if(nums[startIndex] > val) postValCount++;
}else
{
if(nums[startIndex] < val) preValCount++;
if(nums[startIndex] > val) postValCount++;
if(nums[endIndex] < val) preValCount++;
if(nums[endIndex] > val) postValCount++;
}
startIndex++;
endIndex--;
}
if(preValCount + postValCount == nums.length) return new int[]{-1, -1};
return new int[]{preValCount, nums.length - 1 - postValCount};
}
@meekg33k
Copy link

Hey @deedee47, thank you for participating in Week 3 of #AlgorithmFridays.

Your solution definitely works and passes the test cases. However, your current solution requires sorting the array. For improved performance, can you come up with a solution that will not require sorting?

@deedee47
Copy link
Author

deedee47 commented Apr 26, 2021

Hi @meekg33k, thanks alot for the prompt, I did not think of this earlier. The solution has been optimized.

@meekg33k
Copy link

Awesome @deedee47! This is a more optimal solution and yes, you really didn't have to sort the array for this problem; I'm glad you were able to see that.

Because you were able to come up with this solution, you have been selected as one of the winners of the $20 award for Week 3 of #AlgorithmFridays. 🎉🎉

I have written an in-depth blog post here about this solution; the post also announces you as one of the winners. Please read through and let me know what you think.

Thank you for participating once again and see you on Friday for Week 4 of #AlgorithmFridays.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment