---
# System prepended metadata

title: '[4/25, 2:43 PM] Abdelrauf: int'

---

## Pseudo code conventions

******




| Keywords   | Description|
| --- | ----- |
| ---                                                                  | Comment                                                                      |                              |                          |     |       |
| tabs                                                                 | to show blocks                                                               |                              |                          |     |       |
| <-                                                                   | assigment                                                                    |                              |                          |     |       |
| +,-,*, mod, /, and, xor, or                                          | math and bitwise operators                                                   |                              |                          |     |       |
| ( )                                                                  | grouping parenthesis to prevent ambiguity                                    |                              |                          |     |       |
| power(base,x)                                                        | math power                                                                   |                              |                          |     |       |
| **                                                                   | math power that follows python associativity right to left)                  |                              |                          |     |       |
| exp(value)                                                           | e^(value)                                                                    |                              |                          |     |       |
| types: int, float, string, bool, Array, String, Map, Stack, Queue,.. |                                                                              |                              |                          |     |       |
| true, false                                                          | bool type values                                                             |                              |                          |     |       |
| var_name <- value                                                    | type inferenced from value. For example: `a <-1` means it will assume a: int |                              |                          |     |       |
| nums1: Array\[type=int, size=n, sorted\]                             | nums1 is  sorted array of n int elements                                     |                              |                          |     |       |
| nums1: Array\[type=int, size=n\]                                     | nums1 is  array of n int elements initialized with 0                         |                              |                          |     |       |
| str:String                                                           | str is String type.                                                          |                              |                          |     |       |
| #{var_name}                                                          | get the length of Array, String, Stack, Queue                                |                              |                          |     |       |
| array_name\[i\]                                                      | access i-th element of array                                                 |                              |                          |     |       |
| array_name\[m..k\]                                                   | the slice of array from m to k. note: k-th excluded                          |                              |                          |     |       |
| &&,                                                                  |                                                                              | , !=, == or =, >= , <=, <, > | comparison and condition |     | chain |
| if, while, for                                                       | loop and branching                                                           |                              |                          |     |       |
| break, break label |
|continue, continue label | continue skip in the loop|
|if(condition, True case,  False case expression) | short if , or ternary operator
for i in 4..7  | loop i from 4 till 7, 7-th excluded \[4,7\)|
| for x in array | x gets value by iterating array |
| var: type | variable or argument declaration|
|max, min, abs, random_number | builtin functions with the same meaning|
| max a, b  | maximum of a and b |
| min a, b  | minimum of a and b |
|abs x| absolute value of x|
|random_number| get random number|
| function_name(x: type, ...) -> return_type  | function with function_name that accepts x and returns return_type
| function_name var1, ...  | calling function_name with var1 argument
| return ...  | return result from function|
|type UserTypeName| custom type|
|Constructor()| custom type constructor
|Method1(x: type,..) | method names start with capital leter|
|var.Method1 x|calling Method1 with argument x|
|map_name.Contains x| check x key if exists in map `map.Contains(x:any)->bool`|
|stack_name.Push x| pushes x into Stack stack_name |
|string_name.Append x| append into String type|
|x <- stack_name.Pop | pop from Stack stack_name and store into x|
|map1:Map[keyType=int, ValueType=int] | declaration of map|
|map1 <- {key1 -> value1, key2 ->value2, ...} | Map initialization |




## Pseudo codes

### Arrays/String

#### 1) [Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array)
```
merge(nums1: Array[type=int, size=m+n, sorted], 
          m: int, 
      nums2: Array[type=int, size=n, sorted],
          n: int) -> None

    place <- m+n-1
    i <- m-1
    j <- n-1 
    while i>=0 and j>=0 
        if nums2[j]>nums1[i]
            nums1[place] <- nums2[j]
            j <- j-1
        else
            nums1[place] <- nums1[i]
            i <- i-1

        place <- place - 1

    while j>=0
        nums1[place] <- nums2[j]
        j <- j-1
        place <- place - 1
```
    
#### 2) [Remove element](https://leetcode.com/problems/remove-element)
- a)
```
removeElement(self, nums: Array[type=int, size=n], val: int) -> int

    for i in 0..n
        if vec[i] != val
            vec[p] <- vec[i]
            p <- p + 1

    return p

```
- b)
```
removeElement(self, nums: Array[type=int, size=n], val: int) -> int
        place <- n - 1
        for i in n-1..-1
            if nums[i] == val
                    nums[i] <- nums[place]
                    place <- place - 1

    return place+1
```

#### 3) [Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array)

```
removeDuplicates( nums: Array[int, size = n, sorted]) -> int 

    p <- 1
    for i in 1..n
        if nums[i] != nums[p-1]
            nums[p] <- nums[i]
            p <- p+1

    return p

```

#### 4) [Remove Duplicates from Sorted Array 2](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii)
```
removeDuplicates( nums: Array[int, size = n, sorted]) -> int 

    p <- 2
    for i in 2..n
        if nums[i] != nums[p-2]
            nums[p] <- nums[i]
            p <- p+1

    return p

```


#### 5) [Majority element](https://leetcode.com/problems/majority-element/)
```
majorityElement(nums: Array[int, size=n]) -> int
    major <- nums[0]
    count <- 1
    for i in 0..n
        count <- count + if(major=nums[i], 1, -1)
        if count<0
            major <- nums[i]
            count <- 1

    return major
```


#### 6) [Rotate Array](https://leetcode.com/problems/rotate-array)
```
reverse( nums: Array[int, size=n]) -> None
     i <- 0
     j <- n-1 --- #{nums} - 1
     while i<j
        swap nums[i], nums[j]
        i <- i + 1
        j <- j - 1

rotate( nums: Array[int, size=n], k: int) -> None
    end <- #{nums}
    newK <- k mod #{nums}
    reverse nums 
    reverse nums[0..newK]
    reverse nums[newK..end]

```

#### 7) [Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)

```
 maxProfit(prices: Array[int, size=n]) -> int

    diff <- 0
    buy <- max int --- maximumum value
    for i in 0..n
        diff <- max diff, (prices[i] - buy)
        buy <- min buy, prices[i]
    return diff;

```

#### 8) [Best Time to Buy and Sell Stock 2](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii)
- a) 
```
maxProfit(prices: Arrayist[int, size=n]) -> int
    total<- 0
    for i in 1..n
        if prices[i] > prices[i - 1]
            diff <- prices[i] - prices[i - 1]
            total <- total + diff
    return total

```

- b)
```
maxProfit(prices: Arrayist[int, size=n]) -> int
    diff <- 0
    last_min <- prices[0]
    total <- 0
    for i in 1..n
        if prices[i] < prices[i-1]
            diff <- prices[i-1] - last_min
            total <- total + diff
            last_min <- prices[i] --- renew minimum
    diff <- prices[n-1] - last_min
    total <- total + diff
    return total

```

#### 9) [Jump Game](https://leetcode.com/problems/jump-game)

```
canJump(nums: Array[int, size=n]) -> bool
    i <- 0
    max_jump_steps <- 0
    while true
        end_of <- (n - 1 - i)
        max_jump_steps <- max  nums[i], (max_jump_steps - 1) 
        if max_jump_steps >= end_of
            return true
        if max_jump_steps == 0
            return false
        i <- i + 1
    
    return false
```

#### 10) [Jump Game 2](https://leetcode.com/problems/jump-game-ii)

- a)
```
jump(self, nums: Array[int, size=n]) -> int
    max_jump_steps <- 0
    jump_count <- 0
    remain_steps <- 1
    for i in 0..n-1
        max_jump_steps <- max nums[i], (max_jump_steps - 1)
        remain_steps <- remain_steps - 1
        if remain_steps <= 0
            remain_steps <- max_jump_steps
            jump_count <- jump_count + 1

    return jump_count
```
- b)
```
jump(self, nums: Array[int, size=n]) -> int
    max_jump_index <- 0
    jump_count <- 0
    current <- 0
    for i in 0..n
        max_jump_index <- max (i + nums[i]), max_jump_index
        if max_jump_index >= n - 1
            return jump_count + 1
        if i == current
            current <- max_jump_index
            jump_count <- jump_count + 1
    return -1

```

#### 11) [H-Index](https://leetcode.com/problems/h-index)
```
---
```
#### 12) [Insert-Delete-GetRandom O(1)](https://leetcode.com/problems/insert-delete-getrandom-o1)
```

type RandomizedSet

    stack_arr: Stack[int]
    map_index: Map[int -> int]
    
    Constructor()
        --- do nothing or reserve/increase capacity

    Insert(val: int) -> bool
        if map_index.Contains val = False
            return false
        stack_arr.Push val
        map_index[val] <- #{stack_arr}-1
        return true

    Remove(val: int)  -> bool
        if map_index.Contains val = False
            return false

        last_el <- stack_arr[#{stack_arr}-1]
        if last_el != val
            index <- map_index[val]
            map_index[last_el] <- index
            stack_arr[index] <- last_el

        --- erase the last element from stack_arr and map 
        map_index.Remove val;
        stack_arr.Pop
        return true

    GetRandom() -> int
        random_index <- random_number mod #{values}
        return values[random_index];

```

#### 13) [Product Except self Without division operator](https://leetcode.com/problems/product-of-array-except-self)
```
 productExceptSelf(nums: Array[int, size=n]) -> Array[int, size=n]
     
    result: Array[int, size=n]
    x <- 1
    y <- 1
    for i in 0..n
        result[i] <- x
        x <- x * nums[i]
    for i in n-1..-1
        result[i] <- y * result[i]
        y <- y * nums[i]
    
    return result
```

#### 14) [Gas Station](https://leetcode.com/problems/gas-station)
- a)
```
canCompleteCircuit(gas: Array[int, size=n], cost: Array[int, size=n]) -> int
    total_cost <- 0
    total_gas <- 0
    last_index <- 0
    tank <- 0
    for i in 0..n
        total_cost <- total_cost + cost[i]
        total_gas <- total_gas + gas[i]
        tank <- tank + (gas[i] - cost[i])
        if tank < 0
            last_index <- i + 1
            tank <- 0

    if total_gas < total_cost
        return -1

    return last_index
```

- b)
```
canCompleteCircuit(gas: Array[int, size=n], cost: Array[int, size=n]) -> int

    tank <- 0
    j <- 0
    first <- false
    first_attempt_index <- (-1)
    last_index <- (-1)

    for i in 0..2*n
        j <- i mod n
        diff <- gas[j] - cost[j]
        tank <- tank + diff
        if last_index==-1 && diff>=0
            last_index <- j
            tank <- diff
            
            if i>=n && first_attempt_index<=j
                break

            if !first
                first <- true
                first_attempt_index <- j
      
        if tank<0
            last_index <- (-1)

    return last_index

```

#### 15) [Candy](https://leetcode.com/problems/candy)
- a)
```
candy(ratings: Array[int, size=n]) -> int
    up_count <- 0
    down_count <- 0
    peak_count <- 0
    total <- 1
    for i in 1..n-1
        if ratings[i - 1] < ratings[i]
            down_count <- 0
            up_count <- up_count + 1
            peak_count <- up_count + 1
            total <- total + peak_count
        else if ratings[i - 1] == ratings[i]
            down_count <- 0
            up_count <- 0
            peak_count <- 0
            total <- total + 1
        else
            down_count <- down_count  + 1
            up_count <- 0
            total <- total + down_count + if(peak_count <= down_count, 1, 0)
        
    return total
```

- b)
```
candy(ratings: Array[int, size=n]) -> int
    candies: Array[int, size=n]
    --- assumes candies' all elements are 0
    for i in 1..n
        if ratings[i] > ratings[i - 1]
            candies[i] <- candies[i-1] + 1
	
    total <- ratings[n-1]
    for i in n-2..-1
        if ratings[i] > ratings[i + 1]
            candies[i] <- max candies[i], (candies[i+1] + 1)
        total <- total + candies[i]
	  
        
    return total + n
```

#### 16) [Trapping rain water](https://leetcode.com/problems/trapping-rain-water)

- a)
```
trap( height: Array[int, size=n]) -> int
    if n < 1
        return 0
    
    --- forward collect water trapped
    --- between max smaller and max larger

    last_max <- height[0]
    in_between_area <- 0
    trapped_rain <- 0
    for i in 1..n
        if height[i] >= last_max
            trapped_rain <- trapped_rain + in_beetween_area
            last_max <- height[i]
            in_beetween_area <- 0
        else
            in_beetween_area <- in_beetween_area + (last_max - height[i])
            
    --- now collect reverse way 
    --- but without considering equal comparision unlike the first one
    
    last_max <- height[n - 1]
    in_between_area <- 0
    for i in n-2..-1
        if height[i] > last_max
            trapped_rain <- trapped_rain + in_beetween_area
            last_max <- height[i]
            in_beetween_area <- 0
        else
            in_beetween_area <- in_beetween_area + (last_max - height[i])

    return trapped_rain
```
- b)

```
trap( height: Array[int, size=n]) -> int
    if n < 1
        return 0
    first_max <- height[0]
    last_max <- height[n-1]
    first_between_area <- 0
    trapped_rain <- 0
    last_beetween_area <- 0
    for i in 1..n
        if height[i] >= first_max
            trapped_rain <- trapped_rain + first_between_area
            first_max <- height[i]
            first_between_area <- 0
        else
            first_between_area <- first_between_area + (first_max - height[i])
            
        if height[n-1-i] > last_max
            trapped_rain <- trapped_rain + last_beetween_area
            last_max <- height[n-1-i]
            last_beetween_area <- 0
        else
            last_beetween_area <- last_beetween_area + (last_max - height[n-1-i])

    return trapped_rain
```

- c)
```
trap( height: Array[int, size=n]) -> int
    left <- 0
    right <- n - 1
    left_max <- height[left]
    right_max <- height[right]
    water <- 0
    
    while left < right
        if left_max < right_max
            left <- left + 1
            left_max <- max left_max, height[left]
            water <- water + left_max - height[left]
        else
            right <- right - 1
            right_max <- max right_max, height[right]
            water <- water + right_max - height[right]
        
    return water
```


#### 17) [Roman-to-Integer](https://leetcode.com/problems/roman-to-integer)

```
mapper: Map[keyType=char, valueType=int]
mapper <- {
        'I' -> 1,
        'V' -> 5,
        'X' -> 10,
        'L' -> 50,
        'C' -> 100,
        'D' -> 500,
        'M' -> 1000
        }

romanToInt( s: String ) -> int
    number <- 0
    prev <- 0
    for i in 0..#{s}
        x <- mapper[s[i]]
        number <- number + x
        --- adjust before placement
        if prev==1 && (x==5 || x==10) 
                number <- number - prev - prev
        else if prev==10 && (x==50 || x==100)
                number <- number - prev - prev
        else if prev==1 && (x==5 || x==10)
                number <- number - prev - prev
        prev <- x
    
    return number;

```

#### 18) [Integer-to-Roman](https://leetcode.com/problems/integer-to-roman)

- a)
```
intToRoman( num: int ) -> String
    str: String
    ones: Array[type=String]
    tens: Array[type=String]
    hrns: Array[type=String]
    ths:  Array[type=String]

    ones <- {"","I","II","III","IV","V","VI","VII","VIII","IX"}
    tens <-  {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"}
    hrns <-  {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"}
    ths <- {"","M","MM","MMM"}
        
    str.Append ths[num/1000] 
    str.Append hrns[(num mod 1000)/100]
    str.Append tens[(num mod 100)/10]
    str.Append ones[num mod 10]
    
    return str

```

- b)
```

intToRoman( num: int ) -> String
    str: String
    mertebe: Array[type=char]
    beshlik: Array[type=char]
    mertebe <- {' ', 'I', 'X', 'C', 'M'};
    beshlik <- {' ', 'V', 'L', 'D'};
    h <- 1000
    i <- 0
    m <- 4
    while h>0 
        c <- num/h
        num <- num mod h  
        x <- mertebe[m]
        if c==4
            str.Append x
            str.Append beshlik[m]
        else if c==9
            str.Append x
            str.Append mertebe[m+1]           
        else if c>=5
            str.Append beshlik[m]
            for i in 0..c-5
                str.Append x
        else
            for i in 0..c
                str.Append x
        h <- h/10
        m <- (m - 1)
            
    return str


```



