Algorithms Related to Array: Part 1

In this article, I will summarize all the algorithms that are related to array data structure.

What is ARRAY?

First of all, let’s have a definition of ARRAY data structure. ARRAY refers to a collection of data that is kept in a continuous memory space, and as a result you can use subscript index to access each element in the data collection. The first element in the array often begins with 0 (such as C++, Python, etc. NOT MATLAB).

In the following we are going to list algorithms that often use array data structure.

Binary Search

Given a well-sorted array, how can we find the index of the array if the target value happens to be in the array? This is the problem of binary search tries to solve.

The trick part of binary search implementation is to define the search region properly. Suppose left refers to the index of the small value in the current search array while right refers to the index of the largest value plus 1 in the current search array, then the binary search can be implemented in this way:

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left, right=0, len(nums)
        while left<right:
            middle = int((left+right)/2)
            if nums[middle]>target:
                right = middle
            elif nums[middle]<target:
                left = middle+1
            else:
                return middle
           
        return -1

• when the value corresponding to middle index is larger than the target value, it will be regarded as right index for the next search.
• when the value corresponding to middle index is smaller than target value, the middle index plus 1 will become the left index.

Remove Element Problem

If we want to remove one element from an array, how can we do that without allocating memory for a new array? This is what the Remove Element Problem tries to solve.

The solution to this problem is to use double-pointers as the following image shows.

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        new_index = -1 
        for index, value in enumerate(nums):
            if value == val: 
                pass 
            else:
                new_index = new_index+1 
                nums[new_index] = value 
        return new_index+1

• we use double pointers: one quick pointer will point to the original element in the array while one slow pointer will point to the element in the updated array
• the slow pointer will only move forward when the element the fast pointer referring to is different from the target value

Squares of a Sorted Array

Squares of a sorted array is a problem can be solved with double-pointers as well. Assume we are given a sorted numerical array, and we want to have a sorted array that comes from the squares of each element in the given sorted array. The solution using double-pointers is as follows:

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        output = [None]*len(nums)
        ele_sum = len(nums)
        output_index = ele_sum-1
        begin_inc = 0
        end_inc = ele_sum-1
        while(begin_inc<=end_inc):
            begin_value = nums[begin_inc]*nums[begin_inc]
            end_value = nums[end_inc]*nums[end_inc]
            if begin_value>end_value:
                output[output_index] = begin_value
                begin_inc = begin_inc+1
            else:
                output[output_index] = end_value 
                end_inc = end_inc-1
            output_index = output_index-1 
        return output

• the first thought on solving this problem is to calculate the square of the given sorted array first and then sort the newly generated array. The computation cost should be nlog(n).
• using double-pointers can reduce the computation cost to be n.