Skip to content

Instantly share code, notes, and snippets.

Embed
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++;
}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

This comment has been minimized.

Copy link

@meekg33k meekg33k commented Apr 25, 2021

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

This comment has been minimized.

Copy link
Owner Author

@deedee47 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

This comment has been minimized.

Copy link

@meekg33k meekg33k commented Apr 27, 2021

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