# Array & vectors

- Sequential memory locations
- random access by zero based indexing - O(1)
- cache friendly -> improves system level performance asymptotically same
- cache(fastest) -> ram -> hard drive
- in C++ arrays are fixed sized

### Types
- fixed size arrays
- dynamic sized arrays
- c++ - vector
- java - array list
- pythion - list

### Operations
- Search
- unsorted - TC: O(n)
- sorted - TC: O(log n) -> depending on runtime implmentation it can have SC: O(n)
- Insert
- insert in middle or begining - TC: O(n)
- insert when array is not full -> shift elements to right and insert in middle - O(n)
- insert when array is full -> create 2n array and copy all elements in left, insert and insert right elements O(n), Auxillary space -> O(n)
- insert at the end - TC: O(1)
- deletion
- delete at the begining or middle - TC: O(n)
- delete at the end - TC: O(1)
- Getting ith Element: TC: O(1)
- Updating ith element: TC: O(1)

a = [1, 2, 3, 4]

a.append(5)

a.pop() # removes last element and return it

len(a)

a[:] # clone

a[:2] #  first two elements in array # [1, 2]

a[1:3] #  from 1st index element to 3rd index element # [2, 3]

a[-3:] # last three lements


a.index(3) # index of 3 if item not found it throws ValueError exception

filter(None, a) # return list without None values

# Iterate
for i, x in enumerate(nums):
    print(i, x)

for i in range(len(nums)):
    print(i)

for x in nums:
    print(x)

nums.sort() # TC: O(nlogn) SC: O(1) or O(n) depending on runtime implementation
nums.sort(reverse=True)
nums.sort(key=lambda x: x[1])


nums.insert(1, 10) # TC: O(n) SC: O(1)

### Vectors or list or dynamic sized arrays
dynamic sized array implementation is called vectors
- implimentation using arrays or linked list
- array implimentation is prefered because its cache friendly and memory compact since there are no attional pointers

### Operations
- Insert at end -> O(n) worst cast -> O(1) amotized analysis or average case - since we cannot get worst case at each step
- Insert in middle -> O(n)

- Given an array you have to reverse it
- Complexity
- TC - O(n)
- SC - O(1)
- Logic -> two pointer approach, loop from zero to n/2 and swap

def reverse(arr):
    n = len(arr)
    for l in range(n // 2):
        r = n - 1 - i
        arr[l], arr[r] = arr[r], arr[l]
    return arr

- find an element in unsorted array
- complexity
- TC - O(n)
- SC - O(1)
- Logic -> traverse find an element then return true or else reach to end and return false
- worst case is if item is not found or item is last element

# TC: O(n)
# SC: O(1)
def search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

- number of distinct elements
- array of input elements, 0 < arr[i] < 1000.
- Note: use visited array

# TC: O(n)
# SC: O(1)
def count_distinct(arr, target):
    visited = [False] * 1000
    for x in arr:
        if visited[x] == False:
            visited[x] = True
    result = 0
    for x in visited:
        if x == True:
            result += 1
    return result 

- number of element frequency
- array of input elements, 0 < arr[i] < 1000.
- Note: use count array or frequency array

# TC: O(n)
# SC: O(1)
def freqency(arr, target):
    freq = [0] * 1000
    for x in arr:
        visited[x] += 1
    return freq

- sort the array aka bucket search ideal if there are limited charecter set
- array of input elements, 0 < arr[i] < 1000.
- Note: use count array and print them

# TC: O(n)
# SC: O(1)
def sort(arr, target):
    freq = [0] * 1000
    for x in arr:
        visited[x] += 1
    result = []
    for i, x in enumerate(freq):
        if x > 0:
            for j in range(x):
                result.append(i)
    return result 

- find largest element in an array
- TC: O(n) SC: O(1)
- find second largest element in an array
- Two pass method
- first pass find the largest - find the index of largest
- second pass find the second largest - find the index of seond largest which is not the value of first largest element
- TC O(n) SC:(1)
- Single pass
- store the index of largest and second largest
- init largest to first element
- for every element from 1 to last element
- if item is bugger than largest lement
- set seond largest as largest
- set the largest as current
- else if item is equals to largest
- ignore
- else - if less than largest
- if second largest is -1
- assign this is seond largest
- item is equals to second largest then ignore
- item is bigger than second largest
- upddate the seond largest index
- TC: O(n) SC: O(1)
- using min heap of size k (if items are repeated it wont get ignored)
- get subset of array of size k
- heapy the array(min heap)
- loop from k to n
- if current item is bigger than the first object in heap
- pop and push that item in to the heap
- return the first element
- TC: O(k + nlogk), SC: O(k)
- find kth largest element in an array using iteration
- TC: O(kn)
- SC: O(1)

- 2 sum
- 2 loops brute force
- TC: O(n ^ 2)
- SC: O(1)
- hash table two pass
- TC: O(n)
- SC: O(n)
- hash table one pass
- TC: O(n)
- SC: O(n)
- sorted array - two pointer approach
- TC: O(nlogn) O(n) if array is already sorted
- SC: O(1)
- if we are returning index we need to store original index before sorting
- TC: O(nlogn)
- SC: O(n)

TC: O(n)
SC: O(1)
def two_sum(nums, targer):
    l = 0
    r = len(nums) - 1
    while l < r:
        curr_sum = nums[l] + nums[r]
        if curr_sum == target:
            return True
        
        if curr_sum < target:
            l += 1
        else:
            r -= 1
    return False

- intersection
- use frequency array of first array and match with second one
- TC: O(m + m)
- SC: O(max(n, m)) -> result + frequency array
- Can optimize SC: to O(min(m,n)) with simple trick
- sort both the arrays and use two pointer approach
- TC((n + m) log (m + n))
- SC(min(m,n)) -> result

- stock buy sell
- One traversal
- Keep track of global min and max price
- while updating the min dont update the max price since buy and sell should happen on different date

- check if array is sorted
- global_ispositive = None
- loop from 1 to n
- is_positive = current_item - prev
- if global_ispositive is None
- global_ispositive = is_positive
- else:
if global_ispositive != is_positive:
return Fale
- return true
- reverse an array
- contains duplicate in unsorted array
- Naive Solution
- TC: O(n ^2)
- SC: O(1)
- Sort and Search
- TC: O(nlogn)
- SC: O(1)
- hash table to store visited elements
- TC: O(n)
- SC: O(n)
- if n range within constant
- TC: O(n)
- SC: O(1) -> like accii charecters
- remove duplicates from sorted array
- dont create new array of different size
- iterate each element store global prev selement if its repeated then update to None else update the global
- just rearrange the elements and return the new size

- move zeros to end

    count = None
    while i in range(len(arr)):
        if arr[i] != 0:
            arr[i], arr[count] = arr[count], arr[i]
            count += 1

- left rotate an array by 1 postion
- init temp = arr[0]
- for i in range(n)
- arr[i - 1] = arr[i]
- arr[n - 1] = temp
- TC: O(n) SC: O(1)

def rotate_array(arr):
    temp = arr[0]
    for i, x in enumerate(arr):
        if i == 0:
            continue
        arr[i - 1] = x
    arr[len(arr) - 1] = temp

- left rotate an array by k postions
- solution 1
- left rotate d time
- TC: O(nd) SC: O(1)
- solution 2
- init temp = arr[d:]
- for i in range(d, n)
- arr[i - d] = arr[i]
- arr[n - 1] = temp
- TC: O(n) SC: O(d)
- reversal
- reverse(0, d-1)
- reverse(d, n - 1)
- reverse(0, n - 1)
- TC: O(n) SC: O(1)

- leaders in an array
- iterate from right and keep track of the max
- if there are next max then add to leaders

- maximum difference problem with order
- keep track of local min value and global difference
- iterate and update globsl min and max gloval difference
- frequencies in an sorted array
- keep track of last item and last freque
- if items chnage print and init for next
- sock buy or sell
- trapping rain water
- maximum consecutive 1s
- max subarray sum
- solution1
- generate prefix sum
- iterate and update gloval_max diff and global min
- solution2 - kadanes algorithm
- for every item in index
- either take prev_max + arr[i] or [i]
- update gloval max
- max subarray with target sum
- using hash table of prefix sum
- TC: O(n)
- SC: O(n)
- longest even odd subarray
- simiar to maximum consecutive 1s
- max circular sum subraary
- majority element
- min consecutive flips
- sliding window technique
- find the max sum of k consiquitive elements
- given an unsorted array of non-negative integer. if ther eis sum of subarray with given sum
- two pointer right and left
- first keep incrasing the right until sum is greater than target
- keep removing items from left until either its same or smaller
- count distinct elemtns in every window of size k
- n bonacci numbers
- prefix sum technique
- get range sum query
- find if there is an equilibirium point or pivot point
- Can be solved without prefix sum
- calculate total_sum
- iterate through each element
- calculate left_sum
- if left_sum == right_sum
- return index
- update right_sum from the total_sum
- Can be solved with prefix sum
- check if prefix sum of i -1 = suffix_sum of i + 1
- right sum = total sum - left sum
- maximum apperaing element in their range
- check if a given array can be divided into three parts of equal sum
- check if there a subarray with zero sum
- find the longest subarray with equal 0 and 1