Arrays

08 Apr 2019

Reading time ~4 minutes

An array data structure, is a data structure consisting of a collection of elements(values or variables), each identified by at least one array index or key.

One Dimensional Array

Search target in array

When the array is not sorted, we can only use linear search(brutal force) to iterate the whole array to find the target:

int target = 5;
int[] array = new int[] {4,1,5,8,9,0,2}

public bool Exist(int[] arr, int target)
{
    foreach(var num in arr)
    {
        if(num == target) return true;
    }
    return false;
}

When the array is sorted (in increasing or decreasing order), binary search is preferred: int target = 5; int[] array = new int[] {0,1,2,4,5,8,9} // sorted in increasing order

public bool Exist(int[] arr, int target)
{
    var left = 0;
    var right = arr.Length -1;
    while(left < right)
    {
        var mid = (left + right) /2;
        if(arr[mid] == target) return true;
        else if(arr[mid] < target) left = mid +1;
        else right = mid -1;
    }
    return false;
}

[Classic Questions] Determine array is increasing or decreasing (is Monotonic array)

Solution one

1.Two pass

// two for loop for checking an array is increasing or decreasing
 public bool IsMonotonic(int[] A)
        {
            return IsDecreasing(A) || IsIncreasing(A);
        }

        private bool IsIncreasing(int[] a)
        {
            for (int i = 0; i < a.Length - 1; i++)
            {
                if (a[i] > a[i + 1]) return false;
            }
            return true;
        }

        private bool IsDecreasing(int[] a)
        {
            for (int i = a.Length - 1; i >= 1; --i)
            {
                if (a[i] > a[i - 1]) return false;
            }
            return true;
        }

One pass (check comparison result)

 public bool IsMonotonic(int[] A)
        {
            int status = 0; // this status is determined the first time two adjacent elements have different value, then the rest of adjacent value must have same comparison result

            for (int i = 0; i < A.Length - 1; ++i)
            {

                var sign = A[i].CompareTo(A[i + 1]);
                if (sign != 0)
                {
                    if (sign != status && status != 0) return false;
                    status = sign; // status can only change once when two values are different
                }
                
            }
            return true;
        }

Use one

Common strategies to solve `Array` type of questions

Two Pointers

Two pointer technique is an easy and effective technique which is typically used for searching pairs in a sorted arrays.

Example:

977. Squares of a Sorted Array

905. Sort Array By Parity

922. Sort Array By Parity II

167. Two Sum II - Input array is sorted

Frequency List

Build frequency list to find common elements appear in every object (eg: common char in a list of strings) is also a commonly used problem solving technique:

// find all common characters in a list of strings
// ["bella", "label", "roller"] => ["e", "l", "l"]
    var frequencyList = new int[26];
    Array.Fill(frequencyList, int.MaxValue);

        foreach (var str in A)
        {
            var countList = BuildStrFrequencyList(str);
            for (int i = 0; i < frequencyList.Length; i++)
            {
                frequencyList[i] = Math.Min(countList[i], frequencyList[i]);
            }
        }

private int[] BuildStrFrequencyList(string str)
        {
            int[] count = new int[26];
            foreach (var chr in str)
            {
                count[chr - 'a']++;
            }
            return count;
        }

Boyer-Moore Majority Voting Algorithm

Boyer-Moore Majority Voting Algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space. In its simplest form, the algorithm find a majority element in an collection that occurs repeatedly for more than half of the elements of the collection.

Description

The algorithm maintains a local variable majority equals to the first element of the array and a count initially 1. One at a time, the algorithm compares each element in the array and if it’s equal to majority and we increments the count otherwise decrements. When the count is zero we nominate the current element as new majority and set count to 1:

var majority = nums[0];
var count = 1;

for (int i = 1; i < nums.Length; ++i)
{
    if (count == 0)
    {
        majority = nums[i];
        count = 1;
    }
    else if (majority != nums[i])
    {
        --count;
    }
    else ++count;
}
return majority;

Two Dimensional Array aka Matrix & Jagged Array

Common strategies to solve `Multi-dimensional` array questions

Reshape Matrix using `Queue`

One important characteristics of queue is “FIFO”. So it can be used to store the original matrix elements and offer one element at a time with its original sequence in the matrix.