Skip to content

Instantly share code, notes, and snippets.

@chygoz2

chygoz2/startAndEnd.js

Last active Apr 27, 2021
Embed
What would you like to do?
Algo friday 3 solution
const startAndEnd = (nums, val) => {
if (!Array.isArray(nums) || typeof val !== 'number') throw new Error('Invalid input')
const min = Math.min(...nums);
let positions = [-1, -1]
let countLessThanVal = 0
let countOfVal = 0
let countOfMin = 0
for (let num of nums) {
if (num === min) countOfMin++
if (num < val) countLessThanVal++
if (num === val) countOfVal++
}
if (!countOfVal) return positions
positions[0] = val === min ? 0 : countLessThanVal + countOfMin - 1
positions[1] = positions[0] + countOfVal - 1
return positions
}
@meekg33k

This comment has been minimized.

Copy link

@meekg33k meekg33k commented Apr 25, 2021

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

Your solution looks neat in terms of correctness and robustness especially because you handled the edge cases really well. However, what do you think is the time complexity for solution?

Do you think we can do better?

@chygoz2

This comment has been minimized.

Copy link
Owner Author

@chygoz2 chygoz2 commented Apr 25, 2021

Well sorting the array results in a O(nlogn) time complexity, which basically supersedes the linear time complexity due to looping through the array. Unless there's a solution that doesn't involve sorting the array, this is the best I think is obtainable.

@chygoz2

This comment has been minimized.

Copy link
Owner Author

@chygoz2 chygoz2 commented Apr 25, 2021

Update: Solution has been updated, so previous comments are no longer valid.

@meekg33k

This comment has been minimized.

Copy link

@meekg33k meekg33k commented Apr 27, 2021

Hello @chygoz2, congratulations, you are one of the winners of the $20 award for Week 3 of #AlgorithmFridays. 🎉🎉

Your solution was selected because it is most optimal in terms of time complexity. You were able to find a way to solve the problem without sorting the array.

I have written an in-depth blog post here about the solution. The post also announces you as one of the winners for Week 3 of #AlgorithmFridays.

We will contact you in less than 24 hours for your award.

Congratulations once again and thanks for participating!

@chygoz2

This comment has been minimized.

Copy link
Owner Author

@chygoz2 chygoz2 commented Apr 27, 2021

Thank you.

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