order_tree.go

solution.go

package solution

// Performance result:

// N = 30000, weighted 3x. ✔OK
// 1. 0.004 s OK
// 2. 0.004 s OK
// 3. 0.004 s OK
// 4. 0.004 s OK
// 5. 0.004 s OK
// 6. 0.004 s OK
// 7. 0.004 s OK

// N = 60000, weighted 3x. ✔OK
// 1. 0.008 s OK
// 2. 0.012 s OK
// 3. 0.012 s OK
// 4. 0.008 s OK
// 5. 0.012 s OK
// 6. 0.008 s OK
// 7. 0.008 s OK
// 8. 0.008 s OK
// 9. 0.008 s OK

// N = 100000, weighted 3x. ✔OK
// 1. 0.012 s OK
// 2. 0.016 s OK
// 3. 0.016 s OK
// 4. 0.016 s OK
// 5. 0.012 s OK
// 6. 0.012 s OK
// 7. 0.008 s OK
// 8. 0.016 s OK
// 9. 0.012 s OK

// [3, 4, 5, 3] => 1
// [3, 4, 5, 4] => 2
// [3, 4, 5, 3, 4] => 1
// [3, 4, 5, 3, 5] => 0

const null = -1

type backref struct {
	i   int // the index where order is violated
	pi  int // the index for the previous number
	ppi int // the index for the number before previous number}
}

func newref(i int) *backref {
	return &backref{i, null, null}
}

func (r *backref) notNull() bool {
	return r.pi != null || r.ppi != null
}

func Solution(A []int) int {
	refs := make([]*backref, 0)
	// A valid order is no back reference
	for i := range A {
		if i == 0 {
			continue // skip the first
		}
		ref := newref(i)

		if A[i] < A[i-1] {
			ref.pi = i - 1
		}

		if i > 1 && A[i] < A[i-2] {
			ref.ppi = i - 2
		}

		if ref.notNull() {
			refs = append(refs, ref)
		}

		// NOTE: Optimization for early exit, the same logic could be
		// performed at the end of loop.
		if len(refs) > 2 {
			return 0
		}

		if len(refs) == 2 {
			r0 := refs[0]
			r1 := refs[1]

			// The only possible case to continue is when A[r0.pi] is the only violation
			// Example [1, 2, 1, 3, 4]
			//                ^
			if r0.ppi == null && r1.pi == null && r0.pi == r1.ppi {
				continue
			} else {
				return 0
			}
		}
	}

	// The sequence is already sorted
	if len(refs) == 0 {
		return len(A)
	}

	// The only case left from the early exit check.
	if len(refs) == 2 {
		return 1
	}

	// if len(refs) == 1
	ref := refs[0]

	// when there is only one violation, remove either one would work
	if ref.ppi == null {
		return 2
	}

	// when both pi and ppi is not null, must remove this one.
	return 1
}