# Arrays

### What is an Array?

**array:**a collection of items that are stored in neighbouring (contiguous) memory locationssince the items are stored together, checking through the entire collection of items is straightforward

### Python Collections (Arrays)

there are four collection data types in the Python programming language:

**list**: a collection which is ordered and changeableallows duplicate members

**tuple:**a collection which is ordered and unchangeableallows duplicate members

**set:**a collection which is unordered and unindexedno duplicate members

**dictionary:**a collection which is unordered, changeable, and indexedno duplicate members

#### Creating an Array

Note: I will be using a Python List for this page.

### Accessing Elements in Arrays

**index:**a number that identifies each place in an arrayindexing is in the range of

`0`

to`n-1`

where the first place is`0`

, the second place is`1`

, the third place is`2`

, etc.

Example: print the second item of the list:

#### Writing Items into an Array with a Loop

Example: write the first 10 square numbers into a list

#### Reading Items from an Array with a Loop

Example: print out everything that is in `new_list`

Example: a more elegant way of printing out the values of the array

we can use this when we don't need the index values

we can't use this when we are writing the squares into the array since we need the actual index numbers

### Array Length

**length:**the number of item inside the arrayto determine how many items a list has, use the

`len()`

function

Example: print the number of items in the list

#### Handling Array Parameters

most array questions on LeetCode have an array passed in as a parameter

Here is a description for a problem you'll be asked to solve:

Given a binary array, find the maximum number of consecutive 1s in this array.

the only parameter is

`nums`

to iterate through all items in the array, we can do the following:

### Problem: Max Consecutive Ones

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

Note:

the input array will only contain

`0`

and`1`

.the length of input array is a positive integer and will not exceed 10,000

### Problem: Find Numbers with Even Number of Digits

Given an array `nums`

of integers, return how many of them contain an **even number** of digits.

**Example 1:**

**Example 2:**

**Constraints:**

`1 <= nums.length <= 500`

`1 <= nums[i] <= 10^5`

### Problem: Squares of a Sorted Array

Given an array of integers `A`

sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.**
Example 1:**

**Example 2:**

**Note:**

`1 <= A.length <= 10000`

`-10000 <= A[i] <= 10000`

`A`

is sorted in non-decreasing order.

### Basic Array Operations

arrays support the following operations:

insert

delete

search

### Array Insertions

inserting a new element into an array can take many forms:

inserting at the end

inserting at the beginning

inserting at any given index

#### Inserting at the End of the Array

we can add an item to the end of the list using the

`append()`

method

Example: using the `append()`

method to append an item

#### Inserting at the Start of an Array

to insert an element at the start of an array, we'll need to shift the other elements in the array to the right by 1 to make space for the new element

the time taken for insertion at the beginning of the array is proportional to the length of the array

this is linear time complexity:

**O(n)**

to add an item at a specified index, use the

`insert()`

methodto add it to the front of the list, insert at position 0

Example: using `insert()`

to insert at the front of the list

#### Inserting Anywhere in the Array

to insert at any given index, we first need to shift all the elements past that index one position to the right

once the space is created, we insert the new element

inserting at the beginning is a special case of inserting an element at a given index - the given index is

`0`

this is a costly operation since we could

*potentially*have to shift all of the elements to the right before inserting the new elementto add an item at a specified index, use the

`insert()`

method

### Problem: Duplicate Zeros

Given a fixed length array `arr`

of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written.

Do the above modifications to the input array **in place**, do not return anything from your function.

**Example 1:**

**Example 2:**

**Note:**

`1 <= arr.length <= 10000`

`0 <= arr[i] <= 9`

### Problem: Merge Sorted Array

Given two sorted integer arrays *nums1* and *nums2*, merge *nums2* into *nums1* as one sorted array.

**Note:**

The number of elements initialized in

*nums1*and*nums2*are*m*and*n*respectively.You may assume that

*nums1*has enough space (size that is**equal**to*m*+*n*) to hold additional elements from*nums2*.

**Example:**

**Constraints:**

`-10^9 <= nums1[i], nums2[i] <= 10^9`

`nums1.length == m + n`

`nums2.length == n`

## Deleting Items From an Array

### Array Deletions

deleting in an array has the same three different cases:

deleting the last element

deleting the first element

deleting at any given index

#### Deleting From the End of an Array

the least time consuming of the three cases

to remove an item from the end of the list, use the

`pop()`

method

#### Deleting From the Start of an Array

deleting from the front of the array is the costliest operation

it will create a vacant spot at the

`0th`

index and all of the other elements will have to shift one element to the left

shifting all elements will take

**O(n)**time, where**n**is the number of elements in the array

to remove an element from the front of the list, use the

`pop()`

method and pass in`0`

as the index

alternatively, you can use the

`del`

keyword to remove the specified index

#### Deleting From Anywhere in the Array

to delete at any given index, the empty space created by the deleted item will have to be filled

each of the elements to the right of the index we are deleting at will get shifted to the left by 1

deleting the first element of an array is a special case of deletion at a given index, where the index is

`0`

the shift of elements takes

**O(k)**time where**k**is the number of elements to the right of the given indexsince potentially

, we say the time complexity of this operation is also**k = n****O(n)**

Example: deleting the second element in the array using the `pop()`

method

### Problem: Remove Element

Given an array *nums* and a value *val*, remove all instances of that value **in-place** and return the new length.

Do not allocate extra space for another array, you must do this by **modifying the input array ****in-place** with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

**Example 1:**

**Example 2:**

**Clarification:**

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by **reference**, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

### Problem: Remove Duplicates from Sorted Array

Given a sorted array *nums*, remove the duplicates **in-place** such that each element appear only *once* and return the new length.

Do not allocate extra space for another array, you must do this by **modifying the input array ****in-place** with O(1) extra memory.

**Example 1:**

**Example 2:**

**Clarification:**

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by **reference**, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

## Search in an Array

searching is the most important operation

the speed of searching for an element in a data structure helps programmers make design choices for their codebases

there are multiple ways to search an array

**searching**means to find an occurrence of a particular element in the array and return its positionmight need to search an array to find out whether or not an element is present in an array

might want to search an array to find which index to insert a new element at

if we know the index in the array that might have the element we are looking for, the search becomes a constant time operation,

**O(1)**we go to the given index and check whether or not the element is there

### Linear Search

if the index is not known, we can check every element in the array

we continue checking elements until we find the element we're looking for or we reach the end of the array

**linear search algorithm:**technique for finding an element by checking through all elements one by onein the worst case, a linear search checks the entire array

the time complexity for a linear search is

**O(n)**

Example: the linear search algorithm in action, with all the edge cases handled properly.

this is the function we can call to see whether or not an element is in an array

we take care of the edge cases before proceeding with the actual search

we don't check the rest of the elements once we found the element we were looking for

### Binary Search

if the elements in the array are in sorted order, we can use binary search

**binary search:**where we repeatedly look at the middle element in the array and determine whether the element we are looking for is to the left or to the righteach time we do this, we halve the number of elements we need to search, making binary search a lot faster than linear search

only works if the data is sorted

if we are doing a single search, it is faster to do a linear search

it takes longer to sort than to linear search

if we are performing a lot of searches, it is worth sorting the data first so we can use binary search for repeated searches

### Problem: Check if N and Its Double Exist

Given an array `arr`

of integers, check if there exists two integers `N`

and `M`

such that `N`

is the double of `M`

( i.e. `N = 2 * M`

).

More formally check if there exists two indices `i`

and `j`

such that :

`i != j`

`0 <= i, j < arr.length`

`arr[i] == 2 * arr[j]`

**Example 1:**

**Example 2:**

**Example 3:**

**Constraints:**

`2 <= arr.length <= 500`

`-10^3 <= arr[i] <= 10^3`

### Problem: Valid Mountain Array

Given an array `A`

of integers, return `true`

if and only if it is a *valid mountain array*.

Recall that A is a mountain array if and only if:

`A.length >= 3`

There exists some

`i`

with`0 < i < A.length - 1`

such that:`A[0] < A[1] < ... A[i-1] < A[i]`

`A[i] > A[i+1] > ... > A[A.length - 1]`

**Example 1:**

**Example 2:**

**Example 3:**

**Note:**

`0 <= A.length <= 10000`

`0 <= A[i] <= 10000`

Last updated