C

# Welcome to the bytelocker!

This is a small program written in C to help me consolidate by understanding of `FILE` streams, *bitwise operations* and *memory representations* of data.

## What does bytelocker do?

Bytelocker takes in 2 arguments, a file and a password. It then encrypts this file in place with an ECB cipher.

## Why is this useful?

Whilst you can use this binary from the command line to encrypt a standalone file, as is the case with many `C` programs, you will find this integrates nicely within larger workflows. See below.

### My usecase.

I spend my day in vim and vimwiki. And sometimes I need to document slightly sensitive information which I don't feel comfortable leaving in plaintext. As such, I have added a binding to my vimrc calling the bytelocker utility.

The code snippet looks like:
`nnoremap E :silent ! '/Users/aayushbajaj/Google Drive/2. - code/202. - c/202.6 - bytelocker/bytelocker' '%' '$bl_pass'<CR>:set noro<CR>`

here pressing capital E in normal mode will encrypt the file.
- `silent` suppresses output
- `!` is the execution of a shell command, which then runs the bytelocker executable from my google drive
- `%` is a vim macro for the current file
- and the password is retrieved from an environmental variable defined in `.zprofile`.
        - the definition looks like `export bl_pass="passwordpassword"`
        - **NOTE: the password must be 16 characters!!**
        - **NOTE: if you choose to define the password in another file, make sure your viwrc sources the file**
                - the line in .vimrc would look something like `so "~/.config/zsh/.zprofile"


### Demo
![](img/demo.gif)

#include <stdio.h>
#include <stdlib.h>

int upper(int character, int shift) {
        character += shift;
        if (character > 90) {
                character = (character-90)%26 + 64;
        }
        else if (character < 65) {
                character = (65-character)%26;
                if (character == 0) return 65;
                character = 91 - character;
        }
        return character;
}

int lower(int character, int shift) {
        character += shift;
        if (character > 122) {
                character = (character-122)%26 + 96;
        }
        else if (character < 97) {
                character = (97-character)%26;
                if (character == 0) return 97;
                character = 123 - character;
        }
        return character;
}


int main(int argc, char* argv[]) {
        int shift = atoi(argv[1]);
        int character = getchar();
        while (character != EOF) {
                if (character >= 'A' && character <= 'Z') {
                        putchar(upper(character, shift));
                }
                else if (character >= 'a' && character <= 'z') {
                        putchar(lower(character, shift));
                }
                else putchar(character);
                character = getchar();
        }
}

#include <stdio.h>

int main(int argc, char *argv[])
{
    FILE *fi, *fo;
    char *cp;
    int c;

    if ((cp = argv[1]) && *cp!='\0') {
        if ((fi = fopen(argv[2], "rb")) != NULL) {
            if ((fo = fopen(argv[3], "wb")) != NULL) {
                while ((c = getc(fi)) != EOF) {
                    if (!*cp) cp = argv[1];
                    c ^= *(cp++);
                    putc(c,fo);
                }
                fclose(fo);
            }
            fclose(fi);
        }
    }
}

#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

// Macro-defined constants:
#define N_COLS        15
#define N_ROWS        15
#define MAX_SNAKE_LEN (N_COLS * N_ROWS)

#define EMPTY      0
#define SNAKE_HEAD 1
#define SNAKE_BODY 2
#define APPLE      3

#define NORTH 0
#define EAST  1
#define SOUTH 2
#define WEST  3

// Prototypes --- major game operations:
void init_snake(void);
void update_apple(void);
bool update_snake(int direction);
bool move_snake_in_grid(int new_head_row, int new_head_col);
void move_snake_in_array(int new_head_row, int new_head_col);

// Prototypes --- utility functions:
void set_snake(int row, int col, int body_piece);
void set_snake_grid(int row, int col, int body_piece);
void set_snake_array(int row, int col, int nth_body_piece);
void print_grid(void);
int input_direction(void);
int get_d_row(int direction);
int get_d_col(int direction);
void seed_rng(unsigned int seed);
unsigned int rand_value(unsigned int n);

// Constants:
const char symbols[4] = {'.', '#', 'o', '@'};

// Globals:
int8_t grid[N_ROWS][N_COLS] = { EMPTY };

int8_t snake_body_row[MAX_SNAKE_LEN] = { EMPTY };
int8_t snake_body_col[MAX_SNAKE_LEN] = { EMPTY };
int snake_body_len = 0;
int snake_growth   = 0;
int snake_tail     = 0;

// Code:

// `main' (not provided):
// Run the main game loop!
int main(void) {
        init_snake();
        update_apple();

        int direction;
        do {
                print_grid();
                direction = input_direction();
        } while (update_snake(direction));

        int score = snake_body_len / 3;
        printf("Game over! Your score was %d\n", score);

        return 0;
}


// `init_snake' (not provided):
// Set the snake's initial location.
void init_snake(void) {
        set_snake(7, 7, SNAKE_HEAD);
        set_snake(7, 6, SNAKE_BODY);
        set_snake(7, 5, SNAKE_BODY);
        set_snake(7, 4, SNAKE_BODY);
}


// `update_apple' (not provided):
// Pick a random new location to place an apple.
void update_apple(void) {
        int apple_row;
        int apple_col;

        do {
                apple_row = rand_value(N_ROWS);
                apple_col = rand_value(N_COLS);
        } while (grid[apple_row][apple_col] != EMPTY);

        grid[apple_row][apple_col] = APPLE;
}


// `update_snake' (not provided):
// Move the snake one step in `direction' by updating the snake
// locations on the grid and in the array.  Handle consuming apples.
// Trigger a game-over if we wander off the edges of the board.
bool update_snake(int direction) {
        int d_row = get_d_row(direction);
        int d_col = get_d_col(direction);

        int head_row = snake_body_row[0];
        int head_col = snake_body_col[0];

        grid[head_row][head_col] = SNAKE_BODY;

        int new_head_row = head_row + d_row;
        int new_head_col = head_col + d_col;

        if (new_head_row < 0)       return false;
        if (new_head_row >= N_ROWS) return false;
        if (new_head_col < 0)       return false;
        if (new_head_col >= N_COLS) return false;

        // Check if there is an apple where the snake's head will be
        // *before* we move the snake, and thus overwrite the apple.
        bool apple = (grid[new_head_row][new_head_col] == APPLE);

        snake_tail = snake_body_len - 1;

        if (! move_snake_in_grid(new_head_row, new_head_col)) {
                return false;
        }

        move_snake_in_array(new_head_row, new_head_col);

        if (apple) {
                snake_growth += 3;
                update_apple();
        }

        return true;
}


// `move_snake_in_grid' (not provided):
// Paint the snake onto the grid, moving the head along by a step,
// and removing tail segments.  Fail if this move would cause us
// to run into our own body.
bool move_snake_in_grid(int new_head_row, int new_head_col) {
        if (snake_growth > 0) {
                snake_tail++;

                snake_body_len++;
                snake_growth--;
        } else {
                int tail = snake_tail;

                int tail_row = snake_body_row[tail];
                int tail_col = snake_body_col[tail];

                grid[tail_row][tail_col] = EMPTY;
        }

        if (grid[new_head_row][new_head_col] == SNAKE_BODY) {
                return false;
        }

        grid[new_head_row][new_head_col] = SNAKE_HEAD;
        return true;
}


// `move_snake_in_array':
// Update record of where the snake's body segments are, when the head
// is now in a new location.
void move_snake_in_array(int new_head_row, int new_head_col) {
        for (int i = snake_tail; i >= 1; i--) {
                set_snake_array(snake_body_row[i - 1], snake_body_col[i - 1], i);
        }

        set_snake_array(new_head_row, new_head_col, 0);
}


////////////////////////////////////////////////////////////////////////
///
/// The following functions are already implemented in assembly for you.
///
/// You may find it very useful to read through these functions in C and
/// in assembly, but you do not need to do so.
///

// `set_snake' (provided):
// Set up the snake by painting it onto the grid and by recording where
// that piece of the body was.  Only really used in `init_snake'.
void set_snake (int row, int col, int body_piece)
{
        set_snake_grid(row, col, body_piece);
        set_snake_array(row, col, snake_body_len);
        snake_body_len++;
}

// `set_snake_grid' (provided):
// Place `body_piece' into the grid at `row' and `col'.
void set_snake_grid(int row, int col, int body_piece) {
        grid[row][col] = body_piece;
}

// `set_snake_array' (provided):
// Record that the nth piece of the snake's body is at `row' and `col'.
void set_snake_array(int row, int col, int nth_body_piece) {
        snake_body_row[nth_body_piece] = row;
        snake_body_col[nth_body_piece] = col;
}

// `print_grid' (provided):
// Draw the whole grid to the screen.
void print_grid(void) {
        putchar('\n');

        for (int i = 0; i < N_ROWS; i++) {
                for (int j = 0; j < N_COLS; j++) {
                        char symbol = symbols[grid[i][j]];
                        putchar(symbol);
                }

                putchar('\n');
        }
}


int last_direction = EAST;

// `input_direction' (provided):
// Read in the next direction that the user wants to move in.
// Handles invalid input by telling the user their input was bad.
// Handles inputs that the snake cannot move in by going bonk.
int input_direction(void) {
    int direction;
    do {
        if ((direction = getchar()) == EOF) {
            exit (0);
                }

        switch (direction) {
                        case 'w': direction = NORTH; break;
                        case 'a': direction = WEST;  break;
                        case 's': direction = SOUTH; break;
                        case 'd': direction = EAST;  break;

                        case '\n': continue;

                        case '\0':
                        case '\004':
                                exit(0);

                        default: {
                                printf("invalid direction: %c\n", direction);
                                continue;
                        }
                }

                if (
                        0 <= direction && direction <= 3 &&
                        abs(last_direction - direction) != 2
                ) {
            last_direction = direction;
            return direction;
        }

        printf("bonk! cannot turn around 180 degrees\n");
    } while (true);
}


// `get_d_row' (provided):
// Determine the delta-row we want to move to.
int get_d_row(int direction) {
        if (direction == SOUTH) {
                return 1;
        } else if (direction == NORTH) {
                return -1;
        } else {
                return 0;
        }
}

// `get_d_col' (provided):
// Determine the delta-column we want to move to.
int get_d_col(int direction) {
        if (direction == EAST) {
                return 1;
        } else if (direction == WEST) {
                return -1;
        } else {
                return 0;
        }
}


///
/// A very simple pseudo-random number generator.
///
/// `rand_seed', `seed_rng', and `rand_value' implement a pseudo-random
/// number generator --- specifically, a linear congruential generator.
/// (You may like to read more about randomness and random numbers ---
/// it's very interesting!)
///

unsigned int rand_seed = 0;

// `seed_rng' (provided):
// Set the initial seed for our simple pseudo-random number generator.
// This is a bit like `srand(3)', but we can't use that on SPIM.
void seed_rng(unsigned int seed) {
        rand_seed = seed;
}

// `rand_value' (provided):
// Get a random number between 0 and `n', and mix in some randomness.
// This is a bit like `rand(3)', but we can't use that on SPIM.
unsigned int rand_value(unsigned int n) {
        rand_seed = (rand_seed * 1103515245 + 12345) & 0x7FFFFFFF;
        return rand_seed % n;
}

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        table = dict()
        for i, num in enumerate(nums):
            if target - num in table.keys():
                return [i, table[target-num]]
            table[num] = i
        return []

# Definition for singly-linked list.
#class ListNode:
#    def __init__(self, val=0, next=None):
        #self.val = val
        #self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # get numbers out:
        head = l1
        l1_nums = [] # [2,4,3]
        while head:
            l1_nums.append(head.val)
            head = head.next
        print("l1_nums:", l1_nums)
        head = l2
        l2_nums = [] # [5,6,4]
        while head:
            l2_nums.append(head.val)
            head = head.next
        print("l2_nums:", l2_nums)
        # reverse the lists and turn them into ints:
        if l1_nums is not None:
            l1_nums = list(reversed(l1_nums))
        if l2_nums is not None:
            l2_nums = list(reversed(l2_nums))
        l1_num = int(''.join(map(str, l1_nums))) #342
        l2_num = int(''.join(map(str, l2_nums))) #465
        sum = l1_num + l2_num
        sum_list = list(map(int, str(sum)))      # [8, 0, 7]
        #if sum_list is not None:
        #    sum_list = list(reversed(sum_list))  # [7, 0, 8]
        print(sum_list)

        # LN(7) <- LN(0) <- LN(8)

        tail = None
        for i in range(len(sum_list)):
            next = ListNode(sum_list[i], tail)
            i = i + 1
            tail = next

        return tail

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l = r = 0
        longest_length = r - l
        counts = collections.defaultdict(int)
        while r < len(s):
            if counts[s[r]] == 0:
                counts[s[r]] += 1
                r += 1
            else:
                counts[s[l]] = 0
                l += 1
            longest_length = max(r - l, longest_length)

        return longest_length

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int totalSize = nums1Size + nums2Size;
    int merged[totalSize];
    int i = 0, j = 0, k = 0;

    while (i < nums1Size && j < nums2Size) {
        if (nums1[i] < nums2[j]) {
            merged[k++] = nums1[i++];
        } else {
            merged[k++] = nums2[j++];
        }
    }

    while (i < nums1Size) {
        merged[k++] = nums1[i++];
    }

    while (j < nums2Size) {
        merged[k++] = nums2[j++];
    }

    if (totalSize % 2 == 0) {
        return (double)(merged[totalSize/2] + merged[totalSize/2 - 1])/2;
    } else {
        return (double)merged[totalSize/2];
    }
}

class Solution:
    def maxArea(self, height: List[int]) -> int:
        """
        sorted_indices = sorted(range(len(height)),
                                key=lambda index: height[index], reverse=True)
        maxArea = 0
        print(sorted_indices)
        for i, s in enumerate(sorted_indices):
            for j, t in enumerate(sorted_indices):
                if j >= i:
                    container_height = min(height[s],height[t])
                    area = abs(s-t) * container_height
                    if area > maxArea:
                        maxArea = area

        return maxArea

        # Time Limit Exceeded | 54/65 testcases passed
        """
        # two pointer approach
        maxArea = 0
        leftPointer = 0
        rightPointer = len(height)-1
        while leftPointer != rightPointer:
            area = min(height[leftPointer],height[rightPointer]) * abs(leftPointer - rightPointer)
            if area > maxArea:
                maxArea = area
            if height[leftPointer] < height[rightPointer]:
                leftPointer += 1
            else:
                rightPointer -= 1

        return maxArea

#from itertools import combinations
"""
class Solution:

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        def twoSum(numbers: List[int], target: int) -> List[List[int]]:
            res = []
            if not numbers:
                return []
            leftPointer, rightPointer = 0, len(numbers) - 1
            while leftPointer < rightPointer:
                status = numbers[leftPointer] + numbers[rightPointer]
                if status < target:
                    leftPointer += 1
                elif status > target:
                    rightPointer -= 1
                else:
                    res.append([leftPointer + 1, rightPointer + 1])

                    # skip duplicates on BOTH sides
                    lv, rv = numbers[leftPointer], numbers[rightPointer]
                    while leftPointer < rightPointer and numbers[leftPointer] == lv:
                        leftPointer += 1
                    while leftPointer < rightPointer and numbers[rightPointer] == rv:
                        rightPointer -= 1

            return res
        #combinations_of_3 = list(combinations(nums,3))
        #print(len(combinations_of_3))
        #out = []
        #for c in combinations_of_3:
        #    if sum(c) == 0:
        #        if sorted(c) not in out:
        #            out.append(sorted(c))
        #
        #return out

        nums.sort()
        out = []
        for i,n in enumerate(nums):
            if n>0:
                break # sorted, so a positive number means we can never get to 0
            if i>0 and n == nums[i-1]: # skip if same as previous
                continue
            print(nums[i+1:])
            idxs = twoSum(nums[i+1:], 0-n)
            if idxs:
                for idx in idxs:
                    out.append([n, nums[i+idx[0]], nums[i+idx[1]]])

        return out
"""

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        def twoSum(numbers: List[int], target: int) -> List[List[int]]:
            res: List[List[int]] = []
            if not numbers:
                return res
            leftPointer, rightPointer = 0, len(numbers) - 1

            while leftPointer < rightPointer:
                status = numbers[leftPointer] + numbers[rightPointer]
                if status < target:
                    leftPointer += 1
                elif status > target:
                    rightPointer -= 1
                else:
                    # record (keeping your 1-based indexing)
                    res.append([leftPointer + 1, rightPointer + 1])

                    # skip duplicates on BOTH sides
                    lv, rv = numbers[leftPointer], numbers[rightPointer]
                    while leftPointer < rightPointer and numbers[leftPointer] == lv:
                        leftPointer += 1
                    while leftPointer < rightPointer and numbers[rightPointer] == rv:
                        rightPointer -= 1
            return res

        nums.sort()
        out: List[List[int]] = []

        for i, n in enumerate(nums):
            if n > 0:
                break  # remaining numbers are positive → no more triplets
            if i > 0 and n == nums[i - 1]:
                continue  # skip duplicate anchors

            idxs = twoSum(nums[i + 1:], -n)  # search suffix
            for l1, r1 in idxs:               # l1/r1 are 1-based within the suffix
                out.append([n, nums[i + l1], nums[i + r1]])

        return out

class Solution:

    def threeSumClosest(self, nums: List[int], target: int) -> int:

        nums = sorted(nums)

        n = len(nums)
        closest_sum = 9999999

        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue

            lo, hi = i + 1, n - 1

            while lo < hi:
                cur_sum = nums[i] + nums[lo] + nums[hi]

                if abs(cur_sum - target) < abs(closest_sum - target):
                    closest_sum = cur_sum

                if cur_sum == target:
                    return cur_sum
                elif cur_sum < target:
                    lo += 1
                else:
                    hi -= 1

        return closest_sum

def checkGroup(group: List[str]) -> bool:
    print(group)
    uniques = list(set(group))
    counts = {s: group.count(s) for s in uniques}
    del counts['.']
    print(counts.values())
    if any(value > 1 for value in counts.values()):
        print("tripped")
        return False
    if any(int(key) > 9 or int(key) < 1 for key in counts.keys()):
        return False
    return True
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # check rows:
        n = len(board)
        for row in board:
            if not checkGroup(row):
                return False
        # check columns:
        for i in range(n):
            col = [row[i] for row in board]
            if not checkGroup(col):
                return False
        # check grids:
        for row_offset in range(0,n,3):
            for col_offset in range(0,n,3):
                subgrid = []
                for r in range(row_offset, row_offset + 3):
                    for c in range(col_offset, col_offset + 3):
                        subgrid.append(board[r][c])
                if not checkGroup(subgrid):
                    return False
        return True

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        """shockingly this code is accepted despite the O(nlogn) tc and O(n) sc
        # will remove this assumption later:
        nums = sorted(list(set(nums)))

        one = False
        location = 0
        for i, num in enumerate(nums):
            if num == 1:
                one = True
                location = i

        if one == False:
            return 1

        # check subsequent:
        j = location
        spi = 1
        while j < len(nums):
            if nums[j] == spi:
                spi += 1
                j += 1
                continue
            return spi
        return spi
        """

        # cyclic sort:
        n = len(nums)

        # place each positive integer at the respective index within nums
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] -1], nums[i] = nums[i], nums[nums[i] -1] # swap

        # linear search for first discrepancy
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1 # returns discrep

        # or returns n + 1
        return n + 1

class Solution:
    def trap(self, height: List[int]) -> int:
        l_wall = r_wall = 0
        n = len(height)
        max_left = [0] * n
        max_right = [0] * n

        for i in range(n):
            j = -i - 1
            max_left[i] = l_wall
            max_right[j] = r_wall
            l_wall = max(l_wall, height[i])
            r_wall = max(r_wall, height[j])

        summ = 0
        for i in range(n):
            pot = min(max_left[i], max_right[i])
            summ += max(0, pot - height[i])

        return summ

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        """
        #O(mnlogn) sorting bruteforce
        print(strs)
        base = []
        for string in strs:
            base.append("".join((sorted(string))))

        print(base)
        # find indices that are all the same
        idxs = []
        marked = []
        for i, word1 in enumerate(base):
            i_likes = []
            for j, word2 in enumerate(base):
                if word1 == word2 and i <= j and j not in marked:
                    marked.append(j)
                    i_likes.append(j)
            if i_likes:
                idxs.append(i_likes)


        print(idxs)
        # replace indices with words:
        ans = []
        for tup in idxs:
            sublist = []
            for idx in tup:
                sublist.append(strs[idx])
            ans.append(sublist)

        return ans
        """

        # hashmap: O(m*n)
        hash = {}
        for s in strs:

            count = [0] * 26
            for c in s:
                count[ord(c)-ord("a")] += 1

            key = tuple(count)
            if key in hash:
                hash[key].append(s)
            else:
                hash[key] = [s]

        return list(hash.values())

// function to insert value m at position n in array a by shifting the array
void insert(int *a, int m, int n, int l) {
    printf("debug %d %d %d\n", m, n, l);
    int temp = a[l-1];
    for(int i=l-1; i>n; i--) {
        a[i] = a[i-1];
    }
    a[0] = temp;
    a[n] = m;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int p1 = m - 1;
    int p2 = n - 1;

    for (int p = m + n - 1; p >= 0; p--) {
        if (p2 < 0) {break;}
        else {
            nums1[p] = (p1 >= 0 && nums1[p1] > nums2[p2]) ? nums1[p1--] : nums2[p2--];
        }

    }
}

/*
    int offset = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0 + offset; j < n; j++) {
            // if less than first element
            if (i == 0 && nums1[i] >= nums2[j]) {
                printf("insert start\n");
                insert(nums1, nums2[j], i, m + n);
                offset++;
                break;
            }
            // if greater than last element
            else if (i == m - 1 && nums1[i] <= nums2[j]) {
                printf("insert end\n");
                insert(nums1, nums2[j], i, m + n);
                offset++;
                break;
            }
            else if (nums1[i] <= nums2[j] && (i + 1 < m && nums1[i+1] >= nums2[j])){ // belongs in middle
                printf("insert middle\n");
                insert(nums1, nums2[j], i+1, m + n);
                offset++;
                break;
            }
        }
    }
}
*/

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)  # O(n) average time, O(n) space
        longest = 0
        for n in numSet:  # ← iterate uniques to avoid duplicate re-walks
            # check if it is the start of the sequence
            if (n - 1) not in numSet:
                length = 0
                while (n + length) in numSet:
                    length += 1
                longest = max(length, longest)
        return longest

import re
class Solution:
    def reverseWords(self, s: str) -> str:
        splt = re.split('\\s+',s)
        splt.reverse()
        return " ".join(splt).strip()

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        leftPointer, rightPointer = 0, len(numbers) - 1
        while leftPointer != rightPointer:
            status = numbers[leftPointer] + numbers[rightPointer]
            if status < target:
                leftPointer += 1
            elif status > target:
                rightPointer -= 1
            else:
                return [leftPointer+1, rightPointer+1]


        return []

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        """my naive soln
            d = {x:nums.count(x) for x in nums}
            a, b = d.keys(), d.values()
            max_value = max(b)
            max_index = list(b).index(max_value)
            return (list(a)[max_index])

            # o(n^2) because we run o(n) count on each x
        """

        """
        candidate = 0
        count = 0
        # phase 1: find candidate
        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate
        """
        count = {} # dictionary.
        res, maxCount = 0, 0

        for n in nums:
            count[n] = 1 + count.get(n, 0)
            res = n if count[n] > maxCount else res
            maxCount = max(count[n], maxCount)

        return res

class Solution:
    def isHappy(self, n: int) -> bool:
        """
        # N is input size, n is number of digits of N
        visited = set() # O(log n)
        while n != 1:
            m = 0
            if n in visited: # O(1)
                return False
            digits = [int(digit) for digit in str(n)] # O(log n)
            for digit in digits: # O(log n)
                m += digit*digit
            visited.add(n)
            n = m
        return True


        """
        # Time Complexity: O(log n) - number of digits in n
        # Space Complexity: O(log n) - size of visited set

        visited: set[int] = set()  # Track numbers we've seen to detect cycles

        while n not in visited:
            visited.add(n)

            if n == 1:
                return True

            # Calculate sum of squared digits
            current_sum: int = 0
            while n > 0:
                digit: int = n % 10
                current_sum += digit * digit
                n //= 10

            n = current_sum

        return False  # We found a cycle, number is not happy

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode *new = NULL;
    struct ListNode *curr = head;
    while (curr != NULL) {
        struct ListNode *tmp = curr->next;
        curr->next = new;
        new = curr;
        curr = tmp;
    }
    return new;

}

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
          #return True if len(set(nums)) != len(nums) else False
          return len(set(nums)) != len(nums)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        """o(n^2)
        res = [1] * len(nums)
        for i,num in enumerate(nums):
            for j in range(len(nums)):
                res[j] *= (num if i !=j  else 1)

        return res
        """

        """better code, but still not fast enough
        # calculate prefix
        prefix = [0] * (len(nums) + 2)
        prefix[0], prefix[len(nums)+1] = 1,1
        for i in range(len(nums)):
            prefix[i+1] = (nums[i] * prefix[i])

        print(prefix)

        # calculate postfix
        postfix = [0] * (len(nums) + 2)
        postfix[0], postfix[len(nums)+1] = 1,1
        print(postfix)
        for i in reversed(range(len(nums))):
            postfix[i+1] = (nums[i] * postfix[i+2])

        print(postfix)
        # multiply prefix with postfix for each n
        res = [0] * len(nums)
        for i in range(len((nums))):
            print(res)
            res[i] = prefix[i] * postfix[i+2]

        return res
        """

        # the issue above was space complexity.
        # we are going to update the result array for both prefix and postfix

        res = [1] * len(nums)
        # prefix loop:
        for i in range(1, len(nums)):
            res[i] = nums[i-1] * res[i-1]

        postfix = 1
        for j in reversed(range(len(nums)-1)):
            postfix *= nums[j+1]
            res[j] *= postfix


        return res

from collections import deque
#from typing import List
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """anki
        q = deque()
        left = right = 0

        def slide_right():
            nonlocal right
            while q and nums[q[-1]] < nums[right]:
                q.pop()
            q.append(right)
            right += 1

        def slide_left():
            nonlocal left
            left += 1
            if q and left > q[0]:
                q.popleft()

        result = []

        while right < k:
            slide_right()
        result.append(nums[q[0]])

        while right < len(nums):
            slide_right()
            slide_left()
            result.append(nums[q[0]])

        return result
        """
        output = []
        l = r = 0
        q = deque()
        while r < len(nums):
            while q and nums[q[-1]] < nums[r]:
                q.pop()
            q.append(r)

            # remove left val from window
            if l > q[0]:
                q.popleft()

            if (r+1) >= k:
                output.append(nums[q[0]])
                l += 1

            r+= 1
        return output




        """naive
        left = 0
        right = k
        result = []

        N = len(nums)

        while right <= N:
            result.append(max(nums[left:right]))
            left += 1
            right += 1

        return result
        """

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        nums_str = str(nums)
        nums_set = set(nums)
        ans = []
        for i in nums_set:
            if nums_str.count(str(i)) == 1:
                ans.append(i)


        return ans

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return sum(range(len(nums)+1))-sum(nums)

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = []
        for i in range(n+1):
            temp = bin(i)
            ans.append(str(temp)[2:].count('1'))

        return ans

def topKFrequent(nums: List[int], k:int) -> List[int]:
    """
    d = DefaultDict(int)
    for item in nums:
        d[item] += 1
    l = list(sorted(d.items(), key = lambda x: x[1],reverse=True))
    return [x[0] for x in l[:k]]
    """
    # O(nlogn), dominated by the sorting
    # O(n)

    ################################### ###################################
    # O(n) solution via bucket sort:
    # 1. count frequencies O(n)
    frequencies = DefaultDict(int) # lookup failures will be populated with a default int of 0
    for item in nums:
        frequencies[item] += 1

    n = len(nums)

    # 2. create buckets (index = frequency) O(n)
    buckets = [[] for _ in range(n+1)]
    for num, frequency in frequencies.items():
        buckets[frequency].append(num)

    # 3. collect k most frequent items O(n)
    result = []
    while n > -1 and k > 0:
        if buckets[n]:
            result.append(buckets[n].pop())
            k -= 1
        else:
            n -= 1
    return result

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        """reasonably good, but not duplicate resistant code
        matched = 0
        str_idx = -1
        for s_char in s:
            for curr_idx, t_char in enumerate(t):
                if s_char == t_char:
                    if curr_idx > str_idx:
                        str_idx = curr_idx
                        matched += 1
                    else:
                        return False
        if matched == len(s):
            return True
        return False
        """
        matched = 0
        match_idx = 0
        for s_char in s:
            for curr_idx, t_char in enumerate(t[match_idx:]):
                if s_char == t_char:
                    matched += 1
                    match_idx += curr_idx + 1
                    break
        if matched == len(s):
            return True
        return False

from collections import defaultdict
def maxRep(s: str, k: int) -> int:
    count = defaultdict(int)
    max_count = 0
    left = right = 0
    while right < len(s):
        count[s[right]] += 1
        max_count = max(max_count, count[s[right]])
        right += 1
        if right - left - max_count > k:
            count[s[left]] -= 1
            left += 1
    return right - left

import itertools
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        """
        positions = set()
        perms = [''.join(q) for q in itertools.permutations(p)]

        for perm in perms:
            for i in range(len(s)):
                index = s.find(perm, i)
                if index == -1:
                    continue
                if index not in positions:
                    positions.add(index)
                i = index + 1
        return list(positions)
        """
        if len(p) > len(s): return []
        pCount, sCount = {}, {}
        for i in range(len(p)):
            pCount[p[i]] = 1 + pCount.get(p[i],0)
            sCount[s[i]] = 1 + sCount.get(s[i],0)

        res = [0] if sCount == pCount else []
        l = 0

        for r in range(len(p), len(s)):
            sCount[s[r]] = 1 + sCount.get(s[r],0)
            sCount[s[l]] -= 1

            if sCount[s[l]] == 0:
                sCount.pop(s[l])
            l+=1
            if sCount == pCount:
                res.append(l)
        return res

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        missing = []
        """
        hashmap = {}
        for num in nums:
            hashmap[num] = 1
        for i in range(1, len(nums)+1):
            if i not in hashmap:
                missing.append(i)
        return missing
        """
        uniques = set(nums)
        for i in range(1,len(nums)+1):
            if i not in uniques:
                missing.append(i)
        return missing

import itertools
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        """
        if len(s1) == len(s2) and set(s1) != set(s2): return False
        perms = [''.join(q) for q in itertools.permutations(s1)]

        res = False
        for perm in perms:
            print(perm)
            index = s2.find(perm, 0)
            if index != -1:
                res = True
        return res
        """
        n1 = len(s1)
        n2 = len(s2)

        if n1 > n2:
            return False

        s1_counts = [0] * 26
        s2_counts = [0] * 26


        for i in range(n1):
            s1_counts[ord(s1[i])-ord('a')] += 1
            s2_counts[ord(s2[i])-ord('a')] += 1

        if s1_counts == s2_counts:
            return True

        for i in range(n1, n2):
            s2_counts[ord(s2[i]) - ord('a')] += 1
            s2_counts[ord(s2[i - n1]) - ord('a')] -= 1
            if s1_counts == s2_counts:
                return True
        return False