Arrays

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

1. On which memory arrays are created?
   Stack Memory
2. How many ways to find duplicate elements in an array?
   1. Brute Force Method – O(n²)
   2. Using HashSet- O(n)
   3. Using HashMap- O(n)
3. How to search an element in an array
   1. Bruteforce – O(n)
   2. Arrays.binarySearch() -> log(n)
4. Difference between Array & Arraylist
   Array is static and Arraylist is dynamic
5. 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
6. 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)