Introduction

Just like lists are used to organize items in the real world, arrays are used to organize data in computer memory. An Array represents a collection of similar items stored in computer memory.

What is an Array?

Arrays are the building blocks of data structures in computer science. Stacks and LinkedLists are directly derived from arrays. It is used to group similar kinds of data in a contiguous memory location in computer memory for fast access.

  • Each item in an array is called a data element and number of items stored in array is called its size.

  • Each item has a maximum of 2 neighbors other than the first and the last element which only has 1 neighbor.

  • Each data element is assigned an index which signifies it’s position in the array.

  • Index is always non negative, starts from 0 and ends at size - 1. It makes it easy to read a value from array for e.g. array[2], else we would need the traverse the whole data structure.

  • Arrays are stored in memory using a reference pointer, which points to the first element in the array.

Memory allocation for Arrays

To store elements in arrays, we need to first define a chunk of memory as big as the number of items, which reserves the space in memory and creates a pointer to reference the first memory location in that chunk. Then we can store all items in their respective memory locations, each item having it’s own index. This approach enables fast access to each element, all we need to do it specify what index we want to access the value of.

However this also acts as a drawback. If the reserved memory has been exahusted, we would need a define a new array with more memory and then copy all items over to the new array. This is time consuming and ineffective.

Types of Arrays

Arrays can store any type of data including primitive datatypes like int, char, float, short, long, double, byte, bool or non-primitive data type values like Java classes or pointers to other arrays.

  1. one dimensional arrays contains primitive or non-primitive data types
  2. two dimensional arrays contain pointers to other arrays
  3. three dimensional arrays are used to assemble data in a cube-like structure, these are indexed by three variables.

Key Points:

  • 2D array is an array of pointers which hold reference to other arrays, which results in a matrix/table like structure. For example, a matrix that stores student name and a pointer to all the grades in 5 say subjects.
  • All 2D or 3D array values have to be of the same data type.
  • Multi dimensional arrays are widely used in game development.

Sample Definitions (Java)

1D Array

Declaration:

int array[];
or
int[] array;

Instantiation:

int[] array = {1,2,3}; // instantiates as [1,2,3]
or
int[] array = new int[]{1,2,3} // instantiates as [1,2,3]
or
int[] array = new int[3] // instantiates as [0,0,0]

Assignment:

array[0] = 1
array[1] = 2
array[2] = 3  // array now looks like [1, 2, 3]

2D Array

Declaration:

int array[][];
or
int[][] array;

Instantiation:

int[][] array = new int[3][2]	// 3 rows, 2 columns

// this means:
// [0 0]
// [0 0]
// [0 0]

Assignment:

array[0][1] = 10;

// this means:
// [0 10]
// [0 0]
// [0 0]

Common Mistake

One important point to note is that all arrays and (subarrays in case of 2D) must be instantiated before any value assignment or else it will throw an error:

int array[][];

array = new int[3]

for (int i = 0; i < 3; i++) {
	array[i] = new int[2] // instantiation
	array[i][0] = 10 + i // value assignment
	array[i][1] = 20 + i // value assignment
}

// this will result in array[3][2]:
// [10 20]
// [11 21]
// [12 22]

Challenges

Challenges 1 - 10

Challenge 1 : Remove Even Integers from Array

array = [1, 2, 4, 5, 10, 6, 3]
result = [1, 5, 3]


def remove_even(arr):
    numodds = 0
    output = []

    # calculate number of odd items in array
    for x in arr:
        if x % 2 != 0:
            numodds += 1

    # if number of odd items > 0, then add those numbers to output array
    if numodds > 0:
        for x in arr:
            if x % 2 != 0:
                output.append(x)
    else:
        output = "no odds found"

    return output


print("Input: " + str(array))
print("Expected: " + str(result))
print("Output: " + str(remove_even(array)))

First find the number of odd elements in the given array by iterating over it and incrementing a count variable if an element is odd.

Next, initialize an array with a length equal to the quantity of odd numbers in the array, then fill it with the odd numbers in the array.

Time Complexity: O(n)

Output
Input: [1, 2, 4, 5, 10, 6, 3]
Expected: [1, 5, 3]
Output: [1, 5, 3]

Challenge 2 : Merge Two Sorted Arrays

array1 = [1, 3, 4, 5]
array2 = [2, 6, 7, 8]
result = [1, 2, 3, 4, 5, 6, 7, 8]


def merge_sorted(arr1, arr2):
    output = []
    i = 0
    j = 0

    # traverse both arrays together and add
    # the smaller number to output array until
    # one array is complete.
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            output.append(arr1[i])
            i += 1
        else:
            output.append(arr2[j])
            j += 1

    # if first array still has items to be processed,
    # it means they are larger than elements in the second array,
    # so just add them to the result array
    while i < len(arr1):
        output.append(arr1[i])
        i += 1

    # if second array still has items to be processed,
    # it means they are larger than elements in the first array,
    # so just add them to the result array      
    while j < len(arr2):
        output.append(arr2[j])
        j += 1

    return output


print("Input: " + str(array1) + ", " + str(array2))
print("Expected: " + str(result))
print("Output: " + str(merge_sorted(array1, array2)))

We start by creating a new empty array of the size equal to the sum of both sorted arrays passed as the parameters of the function. Starting off from the index 0, individually compare the elements at corresponding indices of both arrays. Place the smaller one in the resultant array, and increment the index of the array where you find the smallest. Keep repeating this till you hit the end of one array. Move the elements of the other array into the resultantArray as it is.

Time Complexity: O(n + m)

Output
Input: [1, 3, 4, 5], [2, 6, 7, 8]
Expected: [1, 2, 3, 4, 5, 6, 7, 8]
Output: [1, 2, 3, 4, 5, 6, 7, 8]

Challenge 3: Find Two Numbers that Add up to “n”

Solution 1: Nested Loop

array = [1, 21, 3, 14, 5, 60, 7, 6]
n = 27
result = "[21, 6] or [6, 21]"

 # iterate both arrays in a nested loop, check for sum == n, return when pair is found
def add_upto_n_1(arr, n):
    output = []

    # select an item in the array and check its sum with
    # every other element in the array, if the sum matches n,
    # then store both items in result and return
    for x in arr:
        for y in arr:
            # note that j = i + 1, this is because we don't
            # need to check the sum of an item with itself and
            # we don't need to check the sum with previous
            # items (as that has already been checked)
            if x + y == n:
                output.append(x)
                output.append(y)
                return output

    return None


print("Input: " + "array = " + str(array) + ", " + "n = " + str(n))
print("Expected: " + str(result))
print("Output: " + str(add_upto_n_1(array, n)))

Traverse the whole array of the given size, for each element in an array and check if any of the two elements add up to the given number n. So, use a nested for-loop and iterate over the entire array for each element.

Time Complexity = O(n^2)

Output
Input: array = [1, 21, 3, 14, 5, 60, 7, 6], n = 27
Expected: [21, 6] or [6, 21]
Output: [21, 6]

Solution 2: Sort => 2 Indices

array = [1, 21, 3, 14, 5, 60, 7, 6]
n = 27
result = "[21, 6] or [6, 21]"

 # step1: sort
 # step2: use 2 indices, one at start, one at end,
 # increment fist if sum < n, decrement second if sum > n, return if sum == n
def add_upto_n_2(arr, n):
    output = []
    i = 0
    j = len(arr) - 1

    arr.sort()

    while i != j:
        if arr[i] + arr[j] < n:
            i += 1
        elif arr[i] + arr[j] > n:
            j -= 1
        else:
            output.append(arr[i])
            output.append(arr[j])
            return output

    return None


print("Input: " + "array = " + str(array) + ", " + "n = " + str(n))
print("Expected: " + str(result))
print("Output: " + str(add_upto_n_2(array, n)))

Solve this by first sorting the array. Then using two variables, one starting from the first index of the array and second from size−1 index of the array. If the sum of the elements on these indexes of the array is smaller than given value n then increment index from the start else decrement index from the end, until the given value n is equal to the sum. Store the elements on these indexes in result array and return it.

For Time Complexity, Algo itself takes O(n) time, Now assuming sort opration takes O(n log(n)) time, for example Quicksort

Time Complexity = O(n log(n))

Output
Input: array = [1, 21, 3, 14, 5, 60, 7, 6], n = 27
Expected: [21, 6] or [6, 21]
Output: [6, 21]

Solution 3: Use Hash Sets

array = [1, 21, 3, 14, 5, 60, 7, 6]
n = 27
result = "[21, 6] or [6, 21]"


 # if n-x in set, implies x is the other number
def add_upto_n_3(arr, n):
    output = []

    x = 0

    # set does not hold duplicates
    temp = set()

    # iterate the array and check if the set contains the value
    # equal to the difference of expected sum and current item.
    # If it exists, add those values to result array and
    # break the loop, else just add the current value to the
    # set to compare in the next iteration.
    for x in arr:
        if n - x in temp:
            output.append(x)
            output.append(n - x)
        else:
            temp.add(x)

    return output


print("Input: " + "array = " + str(array) + ", " + "n = " + str(n))
print("Expected: " + str(result))
print("Output: " + str(add_upto_n_3(array, n)))

Solve this problem by using a HashSet called set. For every element in the arr array, the difference of key & each element (n-arr[i]) is computed. If it’s not already present in the set, this value is added and index moves to the next element of the array.

Note that HashSet is a class of Set interface, therefore it does not allow duplicate values. HashSet is implemented in the backend using a Hash Table. Therefore the lookup time is constant i.e O(1)

As soon as the difference of value stored in set becomes equal to any value in the array arr, the 2 numbers adding up to n are found!

Therefore, an array of size 2 called result is created to store the pair that sums up to ‘n’. If Hash-Set contains an array element, result[] is updated, or else it is returned containing the default value.

The array is iterated over once for each element, so time complexity is O(n).

Time Complexity = O(n)

Output
Input: array = [1, 21, 3, 14, 5, 60, 7, 6], n = 27
Expected: [21, 6] or [6, 21]
Output: [6, 21]

Challenge 4: Array of Products of All Elements Except Itself

Solution 1: Nested Loop

array = [1,2,3,4]
result = [24,12,8,6]


def product_except_itself_1(arr):
    output = []

    # set temp = 1 as a starter
    temp = 1

    # iterate loop twice and multiply inner loop values except itself
    for x in arr:
        for y in arr:
            if x != y:
                temp = temp * y

        output.append(temp)

        # reset temp = 1
        temp = 1;

    return output


print("Input: " + str(array))
print("Expected: " + str(result))
print("Output: " + str(product_except_itself_1(array)))

Time Complexity: O(n^2)

Output
Input: [1, 2, 3, 4]
Expected: [24, 12, 8, 6]
Output: [24, 12, 8, 6]

Solution 2: Sequential Loop

array = [1,2,3,4]
result = [24,12,8,6]


def product_except_itself_2(nums):
    output = []

    # L holds products from left to right
    L = []
    # R holds products from right to left
    R = []

    # initializing temp = 1 and adding it at L[0]
    # adding product of items left of curent index to L
    # computing product of items left of curent index in temp
    temp = 1
    for x in nums:
        L.append(temp)
        temp = temp * x

    # initializing temp = 1 and adding it at R[0]
    # adding product of items right of curent index to R
    # computing product of items right of curent index in temp
    # iterating input array in reverse
    temp = 1
    for y in nums[::-1]:
        R.append(temp)
        temp = temp * y

    # reading L array, reading R array in reverse
    # adding product of each item in both lists to output
    for i in range(len(R)):
        output.append(L[i]*R[len(R)-1-i])

    return output


print("Input: " + str(array))
print("Expected: " + str(result))
print("Output: " + str(product_except_itself_2(array)))

The algorithm for this solution is to first create a new array with products of all elements to the left of each element. Then multiply each element in that array to the product of all the elements to the right of the array by traversing it in reverse.

Time Complexity: O(n)

Output
Input: [1, 2, 3, 4]
Expected: [24, 12, 8, 6]
Output: [24, 12, 8, 6]

Challenge 5 : Find Minimum Value in Array

array = [9, 2, 3, 6]
result = 2


def find_minimum(arr):
    min_value = arr[0]
    for x in arr:
        if x < min_value:
            min_value = x

    return min_value


def main():
    print("Input: " + str(array))
    print("Expected: " + str(result))
    print("Output: " + str(find_minimum(array)))


if __name__ == '__main__':
    main()

Time Complexity: O(n)

Output
Input: [9, 2, 3, 6]
Expected: 2
Output: 2

Challenge 6: First Non-Repeating Integer in an Array

Solution 1: Nested Loops

array = [9, 2, 3, 2, 6, 6]
result = 9


 # using brute force - nested loop
def find_first_unique_1(arr):
    for x in range(0, len(arr)):
        is_unique = True
        for y in range(0, len(arr)):
            if x is not y and arr[x] is arr[y]:
                is_unique = False
                break

        if is_unique:
            return arr[x]

    return None


def main():
    print("Input: " + str(array))
    print("Expected: " + str(result))
    print("Output: " + str(find_first_unique_1(array)))


if __name__ == '__main__':
    main()

Time Complexity: O(n^2)

Output
Input: [9, 2, 3, 2, 6, 6]
Expected: 9
Output: 9

Solution 2: Using Dictionary - HashMap

array = [9, 2, 3, 2, 6, 6]
result = 9


 # Using hash map - dictionary
def find_first_unique_2(arr):
    element_count = {}

    for x in arr:
        element_count[x] = 0

    for x in arr:
        element_count[x] = element_count.get(x) + 1

    for x in arr:
        if element_count.get(x) is 1:
            return x

    return None


def main():
    print("Input: " + str(array))
    print("Expected: " + str(result))
    print("Output: " + str(find_first_unique_2(array)))


if __name__ == '__main__':
    main()

Time Complexity: O(n)

Output
Input: [9, 2, 3, 2, 6, 6]
Expected: 9
Output: 9

Challenge 7: Find Second Maximum Value in an Array

Solution 1: Traversing Array Twice

array = [9, 2, 3, 6]
result = 6


 # traversing array twice
def find_second_max_1(arr):
    maximum = -1
    for x in arr:
        if x > maximum:
            maximum = x

    second_maximum = -1
    for y in arr:
        if second_maximum < y < maximum:
            second_maximum = y

    return second_maximum


def main():
    print("Input: " + str(array))
    print("Expected: " + str(result))
    print("Output: " + str(find_second_max_1(array)))


if __name__ == '__main__':
    main()

Time Complexity: O(n)

Output
Input: [9, 2, 3, 6]
Expected: 6
Output: 6

Solution 2: Traversing Array only Once

array = [9, 2, 3, 6]
result = 6


 # traversing array once
def find_second_max_2(arr):
    maximum = -1
    second_maximum = -1

    for x in arr:
        if x > maximum:
            second_maximum = maximum
            maximum = x
        elif second_maximum < x < maximum:
            second_maximum = x

    return second_maximum


def main():
    print("Input: " + str(array))
    print("Expected: " + str(result))
    print("Output: " + str(find_second_max_2(array)))


if __name__ == '__main__':
    main()

Time Complexity: O(n)

Output
Input: [9, 2, 3, 6]
Expected: 6
Output: 6

Challenge 8: Right Rotate the Array by 1 index

  1. Store the last element in a variable.
  2. Traverse the array backwards and replace element at current index with element and (current - 1) index.
  3. Finally replace the element at 0th index with the temp value stored before.
array = [1, 2, 3, 4, 5]
result = [5, 1, 2, 3, 4]


def right_rotate(arr):
    temp = arr[len(arr)-1]

    index_list = range(len(arr))

    for i in index_list[::-1]:
        arr[i] = arr[i-1]

    arr[0] = temp

    return arr


def main():
    print("Input: " + str(array))
    print("Expected: " + str(result))
    print("Output: " + str(right_rotate(array)))


if __name__ == '__main__':
    main()

Time Complexity: O(n)

Output
Input: [1, 2, 3, 4, 5]
Expected: [5, 1, 2, 3, 4]
Output: [5, 1, 2, 3, 4]

Challenge 9: Re-arrange Positive & Negative Values

Solution 1: Use New Array

  1. Copy Negative elements to temp array
  2. Copy Positive elements to temp array
  3. Copy temp array over original array and return original array
Learn more or give us feedback
array = [10, -1, 20, 4, 5, -9, -6]
result = [-1, -9, -6, 10, 20, 4, 5]


 # using temp array and overwrite on orig
def rearrange_pos_neg_1(arr):
    temp = []
    for x in arr:
        if x < 0:
            temp.append(x)

    for x in arr:
        if x >= 0:
            temp.append(x)

    for y in range(len(temp)):
        arr[y] = temp[y]

    return arr


def main():
    print("Input: " + str(array))
    print("Expected: " + str(result))
    print("Output: " + str(rearrange_pos_neg_1(array)))


if __name__ == '__main__':
    main()

Time Complexity: O(n)

Output
Input: [10, -1, 20, 4, 5, -9, -6]
Expected: [-1, -9, -6, 10, 20, 4, 5]
Output: [-1, -9, -6, 10, 20, 4, 5]

Solution 2: Re-arranging in Place

  1. Use two pointers: 1 to store interation index, 2 to store index of negative numbers being swapped
  2. Traverse the array, if element is negative - swap with last positive element and increment the 2nd index, else move to next interation
array = [10, -1, 20, 4, 5, -9, -6]
result = [-1, -9, -6, 4, 5, 10, 20]


 # in-place swaps
def rearrange_pos_neg_2(arr):
    j = 0
    for i in range(len(arr)):
        if arr[i] < 0:
            if i is not j:
                temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            j += 1
    return arr


def main():
    print("Input: " + str(array))
    print("Expected: " + str(result))
    print("Output: " + str(rearrange_pos_neg_2(array)))


if __name__ == '__main__':
    main()

Time Complexity: O(n)

Output
Input: [10, -1, 20, 4, 5, -9, -6]
Expected: [-1, -9, -6, 10, 20, 4, 5]
Output: [-1, -9, -6, 4, 5, 10, 20]

Challenge 10: Rearrange Sorted Array in Max/Min Form

Solution 1: Using 2 pointers and a switch

Since the array is sorted, smallest elements will be in the beginning and largest at the end.

  1. Set the first pointer to start of array
  2. Set the second pointer to last of array
  3. Set a switch variable to false
  4. Add the element at the first pointer to a temp list, increment the first pointer and flip the switch
  5. In the next iteration, add the element at the second pointer, decrement thte second pointer anf flip the switch
  6. This continues till the array is complete
  7. Now copy the temp array (in max/min form) to the original array and return the array
array = [1,2,3,4,5]
result = [5,1,4,2,3]


 # using 2 pointers and a switch variable
def rearrange_sorted_max_min_1(arr):
    switch = False
    front = 0
    rear = len(arr) - 1
    temp = [0 for x in arr]

    for i in range(len(arr)):
        if switch is False:
            temp[i] = arr[rear]
            rear -= 1
        else:
            temp[i] = arr[front]
            front += 1
        switch = not switch

    for i in range(len(arr)):
        arr[i] = temp[i]

    return arr


def main():
    print("Input: " + str(array))
    print("Expected: " + str(result))
    print("Output: " + str(rearrange_sorted_max_min_1(array)))


if __name__ == '__main__':
    main()

Time Complexity: O(n)

Output
Input: [1, 2, 3, 4, 5]
Expected: [5, 1, 4, 2, 3]
Output: [5, 1, 4, 2, 3]

Solution 2: In-place Replacement

This is a unique solution in which we use multipliers to store the max min element, remainders to store the original elements an division by max element to get the output array in max/min form.

  1. min_index = pointer at start of array
  2. max_index = end of array
  3. max element = element at the last index + 1
  4. we traverse the array in order
  5. for even index: we add (arr[max_index] % max_element) * max_element to the current element at even index, then decrement max_index
  6. for odd index: we add (arr[min_index] % max_element) * max_element to the current element at min_index, then increment min_index
  7. finally we get the max/min array by dividing each value by max_element
array = [1,2,3,4,5]
result = [5,1,4,2,3]


 # in-place replacement
def rearrange_sorted_max_min_2(arr):
    max_index = len(arr) - 1
    min_index = 0
    max_elem = arr[max_index] + 1

    # orig element of stored as remainder, max or min element stored
    # as multiplier, this allows to swap numbers in place, finally
    # divide each element by max element to get output array
    for i in range(len(arr)):
        if i%2 is 0:
            arr[i] += (arr[max_index] % max_elem) * max_elem
            max_index -= 1
        else:
            arr[i] += (arr[min_index] % max_elem) * max_elem
            min_index += 1

    for i in range(len(arr)):
        arr[i] = arr[i] // max_elem

    return arr


def main():
    print("Input: " + str(array))
    print("Expected: " + str(result))
    print("Output: " + str(rearrange_sorted_max_min_2(array)))


if __name__ == '__main__':
    main()

Time Complexity: O(n)

Output
Input: [1, 2, 3, 4, 5]
Expected: [5, 1, 4, 2, 3]
Output: [5, 1, 4, 2, 3]