2.1 array

1. What It Is

• This implements a dynamically resizable array (dynamic array)

2. Dynamic Array

2.1. Data Structure

• Array storing data
• Used length
• Total length

2.2. API

type IArray interface {
	// Print all elements
	String() string
	// Number of used elements
	Length() int
	// Total capacity
	Capacity() int
	// Whether the array is empty
	IsEmpty() bool
	// Add an element at index 0 and shift the others right
	AddFirst(e model.Comparable) error
	// Add an element at index length-1 and shift the others right
	AddLast(e model.Comparable) error
	// Add an element at index and shift the others right
	Add(index int, e model.Comparable) error
	// Get the last element
	GetLast() (model.Comparable, error)
	// Get the first element
	GetFirst() (model.Comparable, error)
	// Get the element at index
	Get(index int) (model.Comparable, error)
	// Set the element at index to e
	Set(index int, e model.Comparable) error
	// Whether the array contains e
	Contains(e model.Comparable) bool
	// Find e and return its index
	Find(e model.Comparable) int
	// Remove the element at index and shift the others left
	Remove(index int) (model.Comparable, error)
	// Remove the element at index 0 and shift the others left
	RemoveFirst() (model.Comparable, error)
	// Remove the element at index length-1 and shift the others left
	RemoveLast() (model.Comparable, error)
	// Remove e and return its index
	RemoveElement(e model.Comparable) int
	// Swap two elements in the array
	swap(i int, j int) error
}

2.3. Implementation

const (
	DefaultSize = 1
	NonExists   = -1
)

type Array struct {
	array    []model.Comparable
	length   int
	capacity int
}

func (a *Array) swap(i int, j int) error {
	if i < 0 || i >= a.Length() || j < 0 || j >= a.Length() {
		return fmt.Errorf("out of bound")
	}
	tmp := a.array[i]
	a.array[i] = a.array[j]
	a.array[j] = tmp
	return nil
}

func NewArray() *Array {
	return &Array{
		array:    make([]model.Comparable, DefaultSize),
		length:   0,
		capacity: DefaultSize,
	}
}

func (a *Array) String() string {
	s := fmt.Sprintf("length=%v, capacity=%v, data=[", a.Length(), a.Capacity())
	for i := 0; i < a.Length(); i++ {
		s += fmt.Sprintf("%v ", a.array[i])
	}
	s = strings.TrimRight(s, " ")
	s += "]"
	return s
}

func (a *Array) Length() int {
	return a.length
}

func (a *Array) Capacity() int {
	return a.capacity
}

func (a *Array) IsEmpty() bool {
	return a.Length() == 0
}

// O(N)
func (a *Array) AddFirst(e model.Comparable) error {
	return a.Add(0, e)
}

// Amortized O(1); O(N) when growing the array
func (a *Array) AddLast(e model.Comparable) error {
	return a.Add(a.Length(), e)
}

// O(N)
func (a *Array) Add(index int, e model.Comparable) error {
	if index < 0 || index > a.Length() {
		return fmt.Errorf("out of bound")
	}

	if a.Length() == a.Capacity() {
		a.resize(a.Capacity() * 2)
	}

	for i := a.Length(); i > index; i-- {
		a.array[i] = a.array[i-1]
	}
	a.array[index] = e
	a.length++

	return nil
}

// O(1)
func (a *Array) GetLast() (model.Comparable, error) {
	return a.Get(a.Length() - 1)
}

// O(1)
func (a *Array) GetFirst() (model.Comparable, error) {
	return a.Get(0)
}

// O(1)
func (a *Array) Get(index int) (model.Comparable, error) {
	if index < 0 || index >= a.Length() {
		return nil, fmt.Errorf("out of bound")
	}

	return a.array[index], nil
}

// O(1)
func (a *Array) Set(index int, e model.Comparable) error {
	if index < 0 || index >= a.Length() {
		return fmt.Errorf("out of bound")
	}

	a.array[index] = e
	return nil
}

// O(N)
func (a *Array) Contains(e model.Comparable) bool {
	return a.Find(e) != NonExists
}

// O(N)
func (a *Array) Find(e model.Comparable) int {
	for i := 0; i < a.Length(); i++ {
		value, _ := a.Get(i)
		if value.CompareTo(e) == 0 {
			return i
		}
	}
	return NonExists
}

// O(N)
func (a *Array) Remove(index int) (model.Comparable, error) {
	if index < 0 || index >= a.Length() {
		return nil, fmt.Errorf("out of bound")
	}
	removed := a.array[index]
	for i := index; i < a.Length()-1; i++ {
		a.array[i] = a.array[i+1]
	}

	a.array[a.Length()-1] = nil
	a.length--
	if a.Length() == a.Capacity()/4 {
		a.resize(a.Capacity() / 2)
	}

	return removed, nil
}

// O(N)
func (a *Array) RemoveFirst() (model.Comparable, error) {
	return a.Remove(0)
}

// Amortized O(1); O(N) when shrinking the array
func (a *Array) RemoveLast() (model.Comparable, error) {
	return a.Remove(a.Length() - 1)
}

// O(N)
func (a *Array) RemoveElement(e model.Comparable) int {
	index := a.Find(e)
	if index == NonExists {
		return NonExists
	}

	a.Remove(index)
	return index

}

func (a *Array) resize(newCapacity int) {
	newArray := make([]model.Comparable, newCapacity)
	for i := 0; i < a.Length(); i++ {
		newArray[i] = a.array[i]
	}
	a.array = newArray
	a.capacity = newCapacity
}

2.3.1. Test

func TestArray(t *testing.T) {
	array := NewArray()
	fmt.Println(array)

	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e0 := model.NewElement(0)
	array.AddLast(e1)
	array.AddLast(e2)
	array.AddFirst(e0)
	fmt.Println(array)

	array.swap(0, array.Length() - 1)
	fmt.Println(array)

	array.RemoveFirst()
	array.RemoveLast()
	fmt.Println(array)

	fmt.Println(array.Contains(e1))
	fmt.Println(array.Find(e1))
	fmt.Println(array.RemoveElement(e1))
	fmt.Println(array)
	fmt.Println(array.IsEmpty())
}

3. Problem-Solving Patterns

3.1. Two Pointers

3.1.1. Same Direction

• 
  • [0, i) is processed data, [i, j) is processed but unnecessary data, and [j, array.length) is unprocessed data
  • Steps
    • Initialize i=0, j=0
    • while j < array.length
      • If array[j] is needed, keep array[i]=array[j], then move i forward
      • Otherwise skip it

3.1.2. Opposite Directions

• 
  • [0, i) and (j, array.length) are processed data, while [i, j] is unprocessed
  • Steps
    • Initialize i=0, j=array.length-1
    • while i<=j
      • Process array[i] and array[j]
      • Move i or j