One minute
Leetcode 915
The idea of this solution is to find the max of the left and then check whether the max is always smaller than all the rights. If it is smaller than all of them return the index (1 indexed).
This can be shown with a picture:
func partitionDisjoint(A []int) int {
max := A[0]
for i := 0; i < len(A); i++ {
shouldReturn := true
if max < A[i] {
max = A[i]
}
for j := i + 1; j < len(A); j++ {
if A[j] < max {
shouldReturn = false
break
}
}
if shouldReturn {
return i + 1
}
}
return -1
}
Read other posts