algoexpert ts solutions

AlgoExpert TS Solutions

About

This repository contains some solutions for the challenges from AlgoExpert Coding Questions.

Note:
I've not finished all challenges yet, and I'm constantly updating this repository with new solutions, new structures, new tests, etc. So, if you want to see the most recent changes, check the last challenge that is marked as completed in the challenge list section below.

Challenge List

? Easy (31)	? Medium (73)	? Hard (58)	? Very Hard (38)
Two Number Sum Validate Subsequence Sorted Squared Array Tournament Winner Non-Constructible Change	Three Number Sum Smallest Difference Move Element To End Monotonic Array Spiral Traverse	Four Number Sum Subarray Sort Largest Range Min Rewards Zigzag Traverse	Apartment Hunting Calendar Matching Waterfall Streams Minimum Area Rectangle Line Through Points
More... Transpose Matrix Find Closest Value In BST Branch Sums Node Depths Evaluate Expression Tree Depth-first Search Minimum Waiting Time Class Photos Tandem Bicycle Optimal Freelancing Remove Duplicates From Linked List Middle Node Nth Fibonacci Product Sum Binary Search Find Three Largest Numbers Bubble Sort Insertion Sort Selection Sort Palindrome Check Caesar Cipher Encryptor Run-Length Encoding Common Characters Generate Document First Non-Repeating Character Semordnilap	More... Longest Peak Array Of Products First Duplicate Value Merge Overlapping Intervals Best Seat Zero Sum Subarray Missing Numbers Majority Element Sweet And Savory BST Construction Validate BST BST Traversal Min Height BST Find Kth Largest Value In BST Reconstruct BST Invert Binary Tree Binary Tree Diameter Find Successor Height Balanced Binary Tree Merge Binary Trees Symmetrical Tree Split Binary Tree Max Subset Sum No Adjacent Number Of Ways To Make Change Min Number Of Coins For Change Levenshtein Distance Number Of Ways To Traverse Graph Kadane's Algorithm Stable internships Union Find Single Cycle Check Breadth-first Search River Sizes Youngest Common Ancestor Remove Islands Cycle In Graph Minimum Passes Of Matrix Two-Colorable Task Assignment Valid Starting City Min Heap Construction Linked List Construction Remove Kth Node From End Sum of Linked Lists Merging Linked Lists Permutations Powerset Phone Number Mnemonics Staircase Traversal Blackjack Probability Reveal Minesweeper Search In Sorted Matrix Three Number Sort Min Max Stack Construction Balanced Brackets Sunset Views Best Digits Sort Stack Next Greater Element Reverse Polish Notation Colliding Asteroids Longest Palindromic Substring Group Anagrams Valid IP Addresses Reverse Words In String Minimum Characters For Words One Edit Suffix Trie Construction	More... Longest Subarray With Sum Knight Connection Count Squares Same BSTs Validate Three Nodes Repair BST Sum BSTs Max Path Sum In Binary Tree Find Nodes Distance K Max Sum Increasing Subsequence Longest Common Subsequence Min Number Of Jumps Water Area Knapsack Problem Disk Stacking Numbers In Pi Maximum Sum Submatrix Maximize Expression Dice Throws Juice Bottling Dijkstra's Algorithm Topological Sort Kruskal's Algorithm Prim's Algorithm Boggle Board Largest Island Continuous Median Sort K-Sorted Array Laptop Rentals Find Loop Reverse Linked List Merge Linked Lists Shift Linked List Lowest Common Manager Interweaving Strings Solve Sudoku Generate Div Tags Ambiguous Measurements Shifted Binary Search Search For Range Quickselect Index Equals Value Quick Sort Heap Sort Radix Sort Shorten Path Largest Rectangle Under Skyline Longest Substring Without Duplication Underscorify Substring Pattern Matcher Multi String Search Longest Most Frequent Prefix Shortest Unique Prefixes	More... Right Smaller Than Iterative In-order Traversal Flatten Binary Tree Right Sibling Tree All Kinds Of Node Depths Compare Leaf Traversal Max Profit With K Transactions Palindrome Partitioning Min Cuts Longest Increasing Subsequence Longest String Chain Square Of Zeroes Knut Morris Pratt Algorithm A* Algorithm Rectangle Mania Detect Arbitrage Two Edge Connected Graph Airport Connections Merge Sorted Arrays LRU Cache Rearrange Linked List Linked List Palindrome Zip Linked List Node Swap Number Of Binary Tree Topologies Non-Attacking Queens Median Of Two Sorted Arrays Optimal Assembly Line Merge Sort Count Inversions Largest Park Smallest Substring Containing Longest Balanced Substring Strings Made Up Of Strings

(back to top)

Features

• Automatic tests after every commit - using Git Hooks and Jest

• Automatic tests after every push - using Github Actions and Jest

• Common folder - to help you reuse code

• Each challenge has its own folder - to help you organize your solutions

• Each challenge has its own test file - to help you run the tests for a specific challenge

• Each challenge has its own case test file - to help you organize your test cases

• Each challenge has its own README.md file - to help you understand the challenge

• Each challenge has its own solution file - to help you write your solution

• Easy to test your solution - just create a new solution file and update the test file with your solution

• Makefile - to help you run the tests, create new challenges and commit your solutions

• Easy to commit your solution - just run make commit and it will commit with the message feat(CHALLENGE_NAME): add solution {SOLUTION_NUMBER}

• Easy to create new challenges - just run make new and it will create the folder, files and README.md file for you, using templates

• Easy to create new solutions - just run make new-solution and it will create the solution file for you, using templates

• Easy to run the tests - just run make test and it will run all tests

• You can customize the templates - just update the scripts/templates folder

• Easy to debug in VSCode - there is a launch.json file with a debug configuration for the current open challenge tab in VSCode

• Auto discover last challenge completed to create new solution when executing make new-solution command

• Auto discover next challenge to be completed to create new challenge when executing make new command

• Auto update solution been tested when executing make new-solution command

(back to top)

Roadmap

• Replicate function assignature from solution-0.ts to new file when executing make new-solution command

• After creating a new challenge, open all new files in VSCode

• Update all challenges with the new structure after finishing the challenge list

• Auto update number of challenges completed in each level after finishing each challenge when executing make commit command

• Move root config files to a .config folder

• Create a docs folder with a README.md file with some tips and tricks

(back to top)

Study Method

My methodfor solving the challenges is:

0. Preparation

1. Create the challenge folder and files (using the make new command)

1. 1st Step

1. Read the challenge description

2. Draw a solution

3. Write the solution in TypeScript without looking at the solution hints

4. Run the tests (using the make test-changed command)

5. Refactor the solution

6. Repeat steps 4 and 5 until all tests pass

7. Evaluate the complexity of the solution

8. Commit the solution (using the make commit command)

2. 2dn Step

1. Verify the solution hints

2. Compare my solution with the solution hints

3. Try to improve my solution or create a new one based on the solution hints (using the make new-solution command)

4. Repeat steps 4 to 10 until I'm satisfied with the solution

5. Commit the solution (using the make commit command)

3. 3rd Step

1. Watch the solution video

2. Implement other solutions from the video or refactor my solution based on the video

3. Commit the solution (using the make commit command)

flowchart LR
    START((Preparation)) --> one
    subgraph one[1st Step]
    A[Read] --> B[Draw]
    B --> C[Code]
    C --> D[Tests]
    D --> C
    D --> I[Complexity]
    I --> R[Commit]
    end
    subgraph two[2nd Step]
    R --> J[Hints]
    J --> K[Compare]
    K --> L[Refactor]
    L --> M[Tests]
    M --> L 
    M --> S[Commit]
    end
    subgraph three[3rd Step]
    S --> N[Video]
    N --> O[Code]
    O --> P[Code/Refactor]
    P --> Q[Tests]
    Q --> P
    Q --> T[Commit]
    end
    one -.-> two
    two -.-> three
    three --> End(((End)))

(back to top)

Technologies

• Node.js

• TypeScript

• Jest

(back to top)

Requirements

• Node.js

(back to top)

Installation

git clone [email protected]:filipe1309/algoexpert-solutions.git

cd algoexpert-solutions

make install

(back to top)

✅ Tests

I have created a Makefile to help you run the tests.

Run all tests:

make test

Run a specific test:

make test t=CHALLENGE_NAME

Example: make test t=two-number-sum

Run changed tests:

make test-changed

(back to top)

Extras

I have also created a Makefile with some extra commands.

Create a new challenge folder and files:

make new [n=CHALLENGE_NAME] [l=CHALLENGE_LEVEL] [c=CHALLENGE_CATEGORY]

Example:
make new (fill the prompts) OR make new n=two-number-sum l=easy c=arrays

Levels: easy, medium, hard, very-hard

This will create:

• a folder (src/easy/two-number-sum)

• a solution-0.ts file (the file where you will write your solution, you can create more if you want and update the test file)

• a test file solution.spec.ts

• a case test file cases.ts

• a README.md file

Commit your solutions:

make commit [m=COMMIT_MESSAGE]

Example:make commit m="feat: add two number sum solution"
if you don't pass the m argument, it will commit with the message
feat(CHALLENGE_NAME): add solution {SOLUTION_NUMBER}

Create new solution:

make new-solution [n=CHALLENGE_NAME_SNAKE] [l=CHALLENGE_LEVEL_LOWER]

Example:make new-solution [l=easy] [n=two-number-sum]OR make new-solution (fill the prompts)

This will create a new solution file solution-{SOLUTION_NUMBER}.ts and update the test file.

If solution-0.ts already exists, it will create solution-1.ts and update index.ts file and the test file. And so on...

---

Help command:

make help

(back to top)

Contributing

Pull requests are welcome. For major changes, please open an issue first to discuss what you would like to change.

Please make sure to update tests as appropriate.

(back to top)

License

MIT

(back to top)

Acknowledgments

• AlgoExpert

• New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

• ShubcoGen Template™

• Git Hooks without extra dependencies like Husky in Node.js project

• TypeScript + Jest

• Testes Unitários com Node.js, Jest e TypeScript

• What is Big O Notation Explained: Space and Time Complexity

• Utilizando Path Mapping no TypeScript

• Paths Mapping

• Module Resolution

• Understanding the Levenshtein Distance Equation for Beginners

• Stable Marriage Problem - Numberphile

• Stable Marriage Problem (the math bit)

(back to top)

About Me

---

Done with  :heart:  by Filipe Leuch Bonfim ?

(back to top)