An array is a collection of data of the same type which are stored at contiguous memory locations.

## Declaration

int arr[] = new int[20];

## Initialization

int [] arr = new int[]{1, 2, 3, 4, 5}

## Time Complexity

Accessing an element | O(1) |

Adding an element | O(n) |

Removing an element | O(n) |

## Arrays class

`asList(`

): Converts array into ArrayList`binarySearch()`

: Performs a binary search on the array`sort(<array>)`

: Sorts array in ascending order

## Questions

- On which memory arrays are created?

Stack Memory - How many ways to find duplicate elements in an array?
- Brute Force Method – O(n
^{2}) - Using HashSet- O(n)
- Using HashMap- O(n)

- Brute Force Method – O(n
- How to search an element in an array
- Bruteforce – O(n)
- Arrays.binarySearch() -> log(n)

- Difference between Array & Arraylist

Array is static and Arraylist is dynamic - What is the equilibrium index of an array

If the sum of lower indices is equal to the sum of higher indices is called the same - Advantages & Disadvantages of an array

(Advantages)

* Can store multiple elements of the same types under a single variable

* Fetch elements using the index

(Disadvantages)

* Mandatory to declare size before using

* static in nature – can’t increase or decrease memory location

* Insertion/deletion are costly O(n)

* allocate more memory than required

Question:

- Is Unique: Check if string has all unique character
- 44 hash table (set)
- 117 (vector / arraylist)
- 132 (n log n)

- Check Permuation: given two string check if one is permutation of other
- 1 : descbie what is means by permutation)
- 84 -> nlogn , another soln is n with some space
- 122 -> hash table
- 131 -> two string that are permutations would have same character, but in different order, can you make the order same?

- URLify: write a method to replace spaces with %20
- 53
- 118

- Palindrome Permutation: given a string write a function to check if it is a permutationof palinrome.

eg: I/P: Tact Coa

Output: true (permutations: “taco cat”, “atco cta”, etc.)- 1.6, 121, 134, 136

- One Away: three types of edits to perform : insert, remove, replace

eg: pale, ple -> true

Pales, pale -> true

Pale, bake -> false- 23
- 97
- 130

- String compression: eg: aabcccccaaa -> a2b1c5a3 (if compressed is not smaller return original
- 92
- 110

- Rotate matrix: given image in NxN, rotate image by 90 degrees, In place
- 51
- 100

- zero matrix: if element in MXN is 0, make entire row and column to 0
- 17
- 74
- 102

- String Rotation: isSubstring method to check for substring is given, for two string s1 and s2 write code to shcek if s2 is a rotation of s1 using only one call to isSubstring (waterbottle is a rotation of erbottlewat”
- 34
- 88
- 104

Collection of the same type of data

- Calculate item index O(1)
- Insert or Delete items at the beginning: O(n)
- Insert or Delete item in middle O(n)
- Insert or Delete item at end O(1)