Skip to content

Instantly share code, notes, and snippets.

Last active April 27, 2021 10:24
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
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++;
if(nums[startIndex] < val) preValCount++;
if(nums[startIndex] > val) postValCount++;
if(nums[endIndex] < val) preValCount++;
if(nums[endIndex] > val) postValCount++;
if(preValCount + postValCount == nums.length) return new int[]{-1, -1};
return new int[]{preValCount, nums.length - 1 - postValCount};
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?

Copy link

deedee47 commented Apr 26, 2021

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

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