/leetcode-solutions

A brief explanation and time complexity of several Leetcode problems

Primary LanguageJava

1. Getting Started

2. Running the code

Simply copy, paste and run the code if running on HackerRank.

If running locally, then:

  • clone the repo git clone https://github.com/mughees-asif/leetcode-solutions.git

  • change directory cd leetcode-solutions

  • run Main.java with your Java compiler/terminal or run the main method in Main.java if using an IDE.

3. Contributing

Everyone is more than welcome to contribute to the solutions.

3.1. Set-up for IntelliJ IDEA:

  1. From the main menu, choose VCS | Get from Version Control > Git > Clone > https://github.com/mughees-asif/hackerrank-solutions.git(click Test to make sure that connection to the remote can be established).

  2. If no project is currently opened, click Get from Version Control on the Welcome screen. In the Get from Version Control dialog, specify the URL of the repository https://github.com/mughees-asif/hackerrank-solutions.git (click Test to make sure that connection to the remote can be established), or select one of the VCS hosting services on the left. If you are already logged in to the selected hosting service, completion will suggest the list of available repositories that you can clone.

  3. Git root mapping will be automatically set to the project root directory.

  4. Optimise or add a different approach to the same solution.

  5. Initiate a pull request.

  6. I will review it and, if applicable, merge the pull request.

4. Key

  • hit the 📝 icon to navigate to the required section.
Topic Location Difficulty level
Arrays 📝 📗
Strings 📝 📗
Sorting and Searching 📝 📗
Dynamic Programming 📝 📗
Math 📝 📗
Trees 📝 📗
Topic Location Difficulty level
Arrays 📝 📙
Strings 📝 📙
Sorting and Searching 📝 📙
Dynamic Programming 📝 📙
Math 📝 📙
Topic Location Difficulty level
Sorting and Searching 📝 📕
Strings 📝 📕

5. Easy Collection 📗

Arrays - back to key

Challenge Explanation Returns Time complexity
Remove Duplicates from Sorted Array push array elements to HashSet -> duplicates automatically removed -> return HashSet.size() length of array w\out duplicates O(n)
Rotate Array use an extra array in which we place every element of the array at its correct position array elements shifted according to given int parameter O(n)
Single Number use the multiplicative properties of the XOR (^) operator single number that occurs only once in the given array O(n)
Two Sum use a HashMap to reduce look-up to O(1) -> initialise a variable to find target - array[i] value -> if HashMap contains the variable, return the index of array[i] & the variable two numbers that add up to the required sum O(n)
Move Zeros if nums[i] != 0, increment the index and equal to lastIndex != 0 -> replace all shifted elements with 0 all 0's moved to the end on the array O(n)
Missing Number initialise new tempArr with length originalArr + 1 -> populate tempArr from originalArr[0] to i + 1 -> return Arrays.mismatch.() missing number O(n)
Rotate Matrix tranpose -> reverse each matrix[i] transposed matrix O(n2)
Intersection of Arrays II Sort both arrays -> initiliase two pointers i, j (one for each array) -> logic check if (arr1[i] > arr[j]) OR (arr1[i] < arr2[j]) -> if both logic checks are false, we have an intersection (common element) array of common elements b/w both input arrays O(n)

Strings - back to key

Challenge Explanation Returns Time complexity
Reverse String reverses a given char array by using the two-pointer method reversed char array O(n)
Reverse Integer parse Integer as a String -> reverse the string using the two-pointer method -> parse reversed String as an Integer -> Note: handles overflow by using try/catch statement reversed Integer O(n)
Valid Anagram push both String objects to char[] -> sort -> check if both equal eachother boolean O(n)
Valid Palindrome remove all non-alphabetical characters using regex (\\W) -> push String object onto Stack -> use loop to concatenate empty String object with characters from stack stack.pop() -> check if both equal eachother boolean O(n)
First Unique Character in a String push string.toCharArray() -> loop and check if (s.indexOf(arr[i]) == s.lastIndexOf(arr[i])) -> return i if unique, else -1 index of the first unique character O(n)
Count and Say use StringBuilder object to append to previous Integer as per the given input int integer as string at specified place O(n)
Longest Common Prefix SOLUTION 1 - rather elegant Binary Search solution here; SOLUTION 2 - minimumLengthOfPrefix by finding String with the least number of chars -> while loop through until firstElement.charAt(i) != lastElement.charAt(i) common chars in all strings O(nm log n) [n = number of strings; m = max. number of chars in any string]

Sorting and Searching - back to key

Challenge Explanation Returns Time complexity
Merge Sorted Array initiliase an array new int[nums1.length] -> Array.copyOfRange() x 2 -> Arrays.sort() merged array O(1)

Dynamic Programming - back to key

Challenge Explanation Returns Time complexity
Climbing The Stairs 1. simple recursion , 2. to reach the ith step -> (i - 1) + (i - 2) -> initialise array with n capacity -> use loop to determine ith element present in arr[n] integer showing the number of step combinations available O(2n) / O(n)
Maximum Subarray use Kadane's Algorithm integer representing the largest sum of a contiguous subarray O(n)
House Robber loop through array with every iteration at i += 2 maximum integer of loot collected O(n)

Math - back to key

Challenge Explanation Returns Time complexity
Fizz Buzz simple boolean logic String list of numbers replaced with FizzBuzz O(n)
Prime Numbers use the Sieve of Eratosthenes algorithm integer showing total no. of prime numbers < method parameter O(n log n)
Pascal's Triangle generate the overall triangle list, which will store each row as a sublist -> check for the special case of 0 -> If numRows > 0, initialize triangle with [1][1] as its first row, and proceed to fill the rows Pascal's Triangle O(numRows2)
Reverse Bits simple bitwise operator usage Reversed Bit O(n)
Hamming Distance use the ^ operator distance b/w two points O(n)

Trees - back to key

Challenge Explanation Returns Time complexity
Maximum Depth of Tree see code for a detailed explanation integer showing the max. depth of given tree O(2n) / O(n)

6. Medium Collection 📙

Arrays - back to key

Challenge Explanation Returns Time complexity
3Sum sort the array -> iterate through the list -> use another two pointers to approach the target list with arrays O(n2)
Spiral Matrix make the spiral algorithm and implement it -> to reduce time complexity from O(n2) to O(n), use a boolean array to check if the position is going out of bounds or into a cell -> great explanation here spiral elements of given matrix O(n)
Subarray Sum Equals K use HashMap -> add nums[i] to total_sum -> if total_sum - target = nums[i], increment counter number of subarrays O(n)
Meeting Rooms II check the comments on the code integer representing the no. of rooms needed O(n log n)
Kth Largest Element in Array SOLUTION 1: Sort the array and return length - k. SOLUTION 2: Use a PriorityQueue (min heap in Java implementation) -> iterate through and .poll() till heap.size() == k kth largest element from an array 1. O(n log n) / 2. O(n)
Container With Most Water use the two-pointer method max area of water in the container O(n)
Trapping Rain Water use the two-pointer method, check out the comments on the code int representing the amount of trapped water O(n)
Permutations Heap's algorithm all possible permutations O(n)
Next Permutation tricky lexographically greater arrangement O(n)
Product of array except self initialise two arrays -> firstArray[i] = products of A[0]..A[i-1], and secondArray[i] = products of A[i+1]..A[LENGTH-1] -> the result is simply firstArray[i] * secondArray[i] product of all elements except input[i] O(n)

Strings - back to key

Challenge Explanation Returns Time complexity
Longest Substring without repeating characters use the sliding window approach longest substring O(n)
String Compression push input[] to LinkedHashMap to preserve order -> map keys and values -> print compressed string O(n)
Sort Characters By Frequency use a HashMap to count occurrences of the char -> compare and print using StringBuilder (avoid string concatenation) descending order of character frequency O(n log n)
Longest Palindromic Substring there are alot of ways to do this problem, most common solutions use dynamic programming -> this solution uses an expandFromTheMiddle helper method -> Leetcode explains it very well: "We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n − 1 such centers. You might be asking why there are 2n − 1 but not n centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as "abba") and its center are between the two 'b's." longest palindromic substring O(n2)
Find And Replace in String an important detail in the question is that there is no overlapping region string O(n * r), n = length of string, r = replacement operations
Word Search II TRIE it available words in the 2D grid O(n)
Multiply Strings solution based on elementary math multiplication, check the code for comments product of the two input strings O(n2)
Decode String account for the 4 types of characters that are encountered using two Stacks decoded string O(n * m) n = length of input string, m = max. value of digit for decoding
Backspace String Comparison use a Stack boolean O(m + n), n & m = length of input strings

Sorting and Searching - back to key

Challenge Explanation Returns Time complexity
Merge Intervals notice for merging, the lastIndex of firstArray >= firstIndex of secondArray -> if you use this logic, it cuts the need to check each interval merged interval array O(n log n)
Top K Frequent Words count occurrences -> check for alphabetical order using custom Comparator in a PriorityQueue -> remove all the elements that are more than K frequency -> reverse result list top K frequent words O(n log K)
Merge Two Sorted Lists recursion 101 merged lists O(m * n), n & m = length of both lists
Reorder Lists find the middle of the list, reverse second part, merge the lists reordered lists O(n)
Find First and Last Position of Element in Sorted Array search, sorted array? -> binary search int array with first and last location O(log n)

Dynamic Programming - back to key

Challenge Explanation Returns Time complexity
Coin Change dynamic programming 101 integer showing the minimum combinations needed to make amount O(n * m), n = size of coins array, m = amount

Math - back to key

Challenge Explanation Returns Time complexity
Add Two Lists elementary addition integer addition O(n)

6. Hard Collection 📕

Strings - back to key

Challenge Explanation Returns Time complexity
Number To Words tl;dr -> check the code - -

Sorting and Searching - back to key

Challenge Explanation Returns Time complexity
Merge K Sorted Lists use a PriorityQueue (min heap) to keep track of the smallest element in each list K merged lists O(n log k), n = no. of nodes, k = no. of lists