lyc0530
Reputation: 13
Find the minimum sum of two non-adjacent elements in an unsorted array in O(n) time?
input : {5,3,1,2,4,1}
output : 2
Is it possible to do this in O(N) time ?
Upvotes: 1
Views: 903
Answers (1)
PidgeyUsedGust
Reputation: 817
You can find the three smallest elements in O(n), also storing their indices. At least two of those will be non-adjacent, so summing them will give the desired result.
Upvotes: 5
Related Questions
- How do I check if an array includes a value in JavaScript?
- What is a plain English explanation of "Big O" notation?
- Loop through an array of strings in Bash?
- How to merge two arrays in JavaScript and de-duplicate items
- How can I pair socks from a pile efficiently?
- How to insert an item into an array at a specific index?
- How to find the sum of an array of numbers
- How can I add new array elements at the beginning of an array in JavaScript?
- How can I find the time complexity of an algorithm?
- What does O(log n) mean exactly?