Mental Gym

Documenting practices on various coding platforms such as LeetCode, Kattis, HackerRank, etc. Additionally, adding code snippets to show how to implement certain data structures and algorithms (DSA) from scratch.

DSA from scratch

Sorting

∏

Category	Algorithm	Description	Implementation Link
Comparison-based	Bubble Sort	Simple comparison-based sorting	Bubble Sort
Comparison-based	Insertion Sort	Builds the final sorted array one item at a time	Insertion Sort
Comparison-based	Selection Sort	Selects the smallest element from an unsorted list in each iteration and places that element at the beginning	Selection Sort
Comparison-based	Merge Sort	Divides the array into halves, sorts them and merges them back together	Merge Sort
Comparison-based	Quick Sort	Divides the array into partitions and sorts them recursively	Quick Sort
Comparison-based	Random Quick Sort	Uses a random pivot to divide the array into partitions and sorts them recursively	Random Quick Sort
Non-comparison-based	Bucket Sort	Distributes elements into buckets and sorts each bucket individually	Bucket Sort
Non-comparison-based	Counting Sort	Counts the number of objects having distinct key values and uses arithmetic to determine the positions of each key	Counting Sort
Non-comparison-based	Radix Sort	Sorts numbers by processing individual digits	Radix Sort

Arrays

Common Operations for Array

Linked List

Singly Linked List

Doubly Linked List

Stack and Queue

Stack using Linked List

Stack using Array

Queue using Linked List

Queue using Array

Deque using Linked List

Deque using Array

Binary Heap

Basic heap properties

Min Heap implementation

Max Heap implementation

HashMap / Hash Table

Direct Addressing Table (simplified hash table)

Common Operations

Creating HashMap using Array

Open Addressing

Separate Chaining

Tree

Binary Tree

Array Representation of Tree

Binary Search Tree

AVL

Graph

Adjacency Matrix

Adjacency List

Graph Traversal DFS

Graph Traversal BFS

Application: Detect Cycle

Application: Topological Sort

Application: Check Bipartite

Single-Source Shortest Path: Bellman Ford

Single-Source Shortest Path: Dijkstra

Single-Source Shortest Path: BFS on unweighted graph

Single-Source Shortest Path: Modified Dijkstra

Single-Source Shortest Path: DFS on weighted trees

Single-Source Shortest Path: DP on DAG

Boilerplate Code

Arrays:

Kadane's Algorithm

• Calculating max sum subarray

Sliding Window

• Fixed size
• Variable size

Prefix Sum

• Range Sum Query

Two Pointers

• 3 different variations of two pointers

Linked List:

LeetCode Questions

Gradually adding the questions in different languages (Python, Julia & C++)

Arrays & Hashing

Question	Description	Difficulty	Type	Solution
1. Two Sum	Find two indices in a vector such that the numbers add up to a target value	Easy	Arrays, Hashing
242. Valid Anagram	Determine if two strings are anagrams of each other	Easy	Hashing
217. Contains Duplicate	Check if a vector contains any duplicates	Easy	Arrays, Hashing
36. Valid Sudoku	Determine if a 9x9 Sudoku board is valid	Medium	Arrays, Hashing
128. Longest Consecutive Sequence	Find the length of the longest consecutive elements sequence	Medium	Arrays, Hashing
271. Encode and Decode Strings	Encode a list of strings to a single string and decode it back to the list	Medium	Arrays, String Manipulation
49. Group Anagrams	Group strings into anagrams	Medium	Hashing, Sorting
219. Close Duplicates	Check if a vector contains duplicates within a given range	Easy	Sliding Window
1343. NumOfSubarrays	Count subarrays with average greater than or equal to a threshold	Medium	Sliding Window
1929. Concatenation of Array	Return array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i]	Easy	Arrays

Two Pointers

Question	Description	Difficulty	Type	Solution
125. Valid Palindrome	Determine if a string is a palindrome, considering only alphanumeric characters and ignoring cases	Easy	Two Pointers
15. Three Sum	Find all unique triplets in the array which gives the sum of zero	Medium	Two Pointers
11. Container With Most Water	Find two lines that together with the x-axis form a container, such that the container contains the most water	Medium	Two Pointers
Two Sum Part 2	Find two indices in a sorted array such that they add up to a specific target	Medium	Sliding Window
Trapping Rain Water	Calculate how much water can be trapped after raining	Hard	Sliding Window

Stack

Question	Description	Difficulty	Type	Solution
20. Valid Parenthesis	Determine if the input string has valid parentheses	Easy	Stack
155. Min Stack	Build a stack that supports push, pop, top, and retrieve the minimum in O(1) time	Easy	Stack
150. Evaluate RPN	Evaluate Reverse Polish Notation expression	Medium	Stack

Sliding Window

Question	Description	Difficulty	Type	Solution
121. Best Time to Buy and Sell Stock	Find the maximum profit you can achieve from one transaction	Easy	Sliding Window
3. Longest Substring Without Repeating Characters	Find the length of the longest substring without repeating characters	Medium	Sliding Window
424. Longest Repeating Character Replacement	Find the length of the longest substring containing the same letter you can get after performing k replacements	Medium	Sliding Window
76. Minimum Window Substring	Find the minimum window substring of s such that every character in t is included	Hard	Sliding Window
567. Permutation in String	Check if one string is a permutation of a substring of another string	Medium	Sliding Window
239. Sliding Window Maximum	Find the maximum value in each sliding window of a fixed size k.	Hard	Sliding Window

Linked List

Question	Description	Difficulty	Type	Solution
21. Merge Two Sorted Lists	Merge two sorted linked lists and return it as a new sorted list	Easy	Linked List

Kattis Problems

Kattis Problems

Problem ID	Description	Difficulty	Type	Solution
hip hip	Print "Hipp hipp hurra!" 20 times	Easy	Easy Coding Challenges
storafmaeli	Check if it's anniversary	Easy	Easy Coding Challenges
fyrirtækjanafn	Filter out consonants from input	Easy	Easy Coding Challenges
peningar	Calculate values accumulated from circular cells	Easy	Easy Coding Challenges
framvindustika	Print progress bar and %	Medium	Easy Coding Challenges
message	Extract letters from nested list to form a message	Easy	Easy Coding Challenges
bidendalausbid	Calculate waited time in minutes	Easy	Easy Coding Challenges
hlaupafmaeli	Check birthday for leap year	Medium	Easy Coding Challenges
lidaskipting2	Find min and max number of competitive teams that can be formed	Easy	Easy Coding Challenges
fleytitala	Find min and max number of competitive teams that can be formed	Medium	Easy Coding Challenges
subaruba	Ubbi dubbi game	Medium	Array
gangur	Count passing pairs of people	Easy	Array
taktsvedjur	Calculate scores with multipliers	Easy	Array