Solutions to the InterviewBit problems in Java
- Bit Manipulation
- Array
- String
- Linked List
- Stack
- Queue
- Heap
- Trees
- Hash Map
- Hashing
- Math
- Two Pointers
- Sort
- Recursion
- Binary Search
- Binary Search Tree
- Breadth-First Search
- Depth-First Search
- Backtracking
- Dynamic Programming
- Greedy
- Graph
- Geometry
- Simulation
- Design
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | Spiral Array | Java | O(n*m) | O(1) | Easy | |
| 2 | Min Steps | Java | O(n) | O(1) | Easy | |
| 3 | Add One to Number | Java | O(n) | O(1) | Easy | |
| 4 | Max Sum Contiguous Subarray | Java | O(n) | O(1) | Medium | Kadane's Algo :- previous MSS should be positive for optimal subarray |
| 5 | Maximum Absolute Difference | Java | O(n) | O(1) | Medium | Carefully look the given exp and how it can be written down |
| 6 | Repeat and Missing Number Array | Java | O(n) | O(1) | Medium | Look for overflows and equations |
| 7 | Flip | Java | O(n) | O(1) | Medium | |
| 7 | Max Non Negative SubArray | Java | O(n) | O(1) | Easy | Check for overflows and tie constraints properly |
| 8 | Spiral Order Matrix II | Java | O(n*n) | O(n*n) | Easy | |
| 9 | Pascal Triangle | Java | O(n*n) | O(n*n) | Easy | |
| 10 | Kth Row of Pascal's Triangle | Java | O(n*n) | O(n) | Easy | Think in terms of if previous calculated list is needed or not |
| 11 | Anti Diagonals | Java | O(n) | O(1) | Easy | |
| 12 | Noble Integer | Java | O(nlogn) | O(1) | Easy | |
| 13 | Triplets with Sum between given range | Java | O(n) | O(1) | Medium | Bookmarked |
| 14 | Largest Number | Java | O(n) | O(n) | Medium | Comparator |
| 15 | Wave Array | Java | O(nlogn) | O(1) | Easy | |
| 16 | Hotel Bookings Possible | Java | O(nlogn) | O(1) | Medium | Bookmarked |
| 17 | Find Duplicate in Array | Java | O(n) | O(1) | Easy | |
| 18 | Max Distance | Java | O(n) | O(n) | Medium | Bookmarked |
| 19 | Min Unsorted Subarray | Java | O(n) | O(n) | Medium | Bookmarked |
| 20 | Maximum Consecutive Gap | Java | O(n) | O(n) | Medium | Bookmarked, PigeonHole Sorting using bucket method |
| 21 | Rotate Matrix | Java | O(n*n) | O(1) | Medium | Good Question |
| 22 | MAXSPPROD | Java | O(n) | O(n) | Medium | Good Question |
| 23 | Next Permutation | Java | O(nlogn)(only if already highest perm, else O(n + logn)) | O(1) | Medium | Good Question, Analyse diff examples, Bookmarked |
| 24 | Find Permutation | Java | O(n) | O(1) | Medium | Good Question, Bookmarked |
| 25 | Set Matrix Zeros | Java | O(n*m) | O(1) | Medium | Good Question |
| 26 | First Missing Integer | Java | O(n) | O(1) | Medium | Good Question, Bookmarked |
| 27 | Merge Overlapping Intervals | Java | O(nlogn) | O(1) | Medium | Good Question, Bookmarked |
| 28 | Merge Intervals | Java | O(n) | O(1) | Medium | Good Question, Good Edge Cases |
| 29 | N/3 Repeat Number | Java | O(n) | O(1) | Medium | Good Question, Moore's Voting Algo |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | All Factors | Java | O(sqrt(n)) | O(1) | Easy | Keep notice of edge cases - like i^2 = A |
| 2 | Binary Representation | Java | O(log(n)) | O(1) | Easy | |
| 3 | Prime | Java | O(sqrt(N)loglog(n)) | O(1) | Easy | Sieve of Eratosthenes |
| 4 | Verify Prime | Java | O(sqrt(N)) | O(1) | Easy | |
| 5 | Prime Sum | Java | O(sqrt(N)loglog(n) + N) | O(1) | Easy | |
| 6 | Sum of pairwise Hamming Distance | Java | O(N) | O(1) | Medium | Good idea on how to use mod for large test cases, and good solution |
| 7 | FizzBuzz | Java | O(N) | O(1) | Easy | |
| 8 | Power Of Two Integers | Java | O(sqrt(N)*log(N)) | O(1) | Easy | Think easy solution |
| 9 | Excel Column Number | Java | O(N) | O(1) | Easy | |
| 10 | Excel Column Title | Java | O(logn) | O(1) | Easy | Good Question |
| 11 | Palindrome Integer | Java | O(number of digits) | O(1) | Easy | |
| 12 | Reverse Integer | Java | O(number of digits) | O(1) | Easy | |
| 13 | GCD | Java | O(log(min a,b)) | O(1) | Easy | Eucledian Algo, Good Question |
| 14 | Trailing Zeroes | Java | O((A)^1/5) | O(1) | Easy | Good Question |
| 15 | Sorted Permutation Rank | Java | O(A^2) | O(1) | Medium | Good Question, Consider usage of factorial in case of modulo |
| 16 | Largest Coprime Divisor | Java | O(A^2) | O(1) | Medium | Bookmarked |
| 17 | Sorted Permutation Rank with Repeats | Java | O(A^2) | O(1) | Medium | Bookmarked, Multiplicative Inverse Modulo(use long in case of modulo) |
| 18 | ReArrange Array | Java | O(A) | O(1) | Medium | Bookmarked, Encoding 2 values in one |
| 19 | Grid Unique Paths | Java | O(min(row,col)) | O(1) | Easy | Bookmarked, DP or Combinatorial |
| 20 | Numbers of length N and value less than K | Java | O(B) | O(1) | Medium | Bookmarked |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | SQRT | Java | O(log(n)) | O(1) | Easy | Keep check for out of range in case of Multiplication else use division |
| 2 | Count Element Occurence | Java | O(log(n)) | O(1) | Easy | |
| 3 | Rotated Array | Java | O(log(n)) | O(1) | Easy | Bookmarked |
| 4 | Matrix Median | Java | O(log(2^32)rlog(c)) = O(32 * r * log(c)) | O(1) | Medium | Bookmarked |
| 5 | Matrix Search | Java | O(log(rc)) = O(log(r) + log(c)) | O(1) | Easy | Bookmarked |
| 6 | Sorted Insert Position | Java | O(log(n)) | O(1) | Easy | |
| 7 | Implement Power Function | Java | O(log(power)) | O(1) | Easy | Handle Negative value carefully, Bookmarked |
| 8 | Rotated Sorted Array Search | Java | O(log(n)) | O(1) | Easy | |
| 9 | Search for a Range | Java | O(log(n)) | O(1) | Easy | |
| 10 | Painter's Partition Problem | Java | O(Nlog(sum(array))) | O(1) | Medium | Bookmarked, Example to use BS in monotonic functions |
| 11 | Allocate Books | Java | O(Nlog(sum(array))) | O(1) | Medium | Bookmarked, Example to use BS in monotonic functions |
| 12 | Median of Array | Java | O(log(m+n)) | O(1) | Hard | Bookmarked |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | Palindrome String | Java | O(n) | O(1) | Easy | |
| 2 | Longest Common Prefix | Java | O(n*min(String Length)) | O(1) | Easy | |
| 3 | Count And Say | Java | O(n*max(String Length)) | O(1) | Easy | |
| 4 | Minimum Characters required to make a String Palindromic | Java | O(n) | O(1) | Easy | |
| 5 | Longest Palindromic Substring | Java | O(n*n) | O(1) | Medium | Bookmarked, 1 length is always palindrome |
| 6 | StrStr | Java | O(n) | O(m) | Medium | Bookmarked, KMP Algo |
| 7 | Compare Version Numbers | Java | O(n) | O(n) | Medium | Bookmarked |
| 8 | Atoi | Java | O(n) | O(1) | Easy | Bookmarked |
| 9 | Length of Last Word | Java | O(n) | O(1) | Easy | |
| 10 | Reverse the String | Java | O(n) | O(n) | Easy | Bookmarked, Ask if split function can be used |
| 11 | Valid Number | Java | O(n) | O(1) | Easy | Bookmarked, Lots of corner cases |
| 12 | Valid Ip Addresses | Java | O(n) | O(1) | Easy | Bookmarked, Placing 3 dots |
| 13 | Roman To Integer | Java | O(n) | O(1) | Easy | Bookmarked |
| 14 | Integer To Roman | Java | O(n) | O(1) | Easy | Bookmarked, Ask if you can have diff arrays to store value |
| 15 | Add Binary Strings | Java | O(n) | O(1) | Easy | Bookmarked, Shorter Solution |
| 16 | Power of 2 | Java | O(logn) | O(1) | Easy | Bookmarked, Use of CompareTo function |
| 17 | Multiply Strings | Java | O(n*m) | O(1) | Easy | Bookmarked |
| 18 | Justified Text | Java | O(n*n) | O(n) | HARD | Bookmarked, Used Greedy Approach |
| 19 | ZigZag String | Java | O(n) | O(1) | Medium | Bookmarked |
| 20 | Pretty Json | Java | O(n) | O(1) | Medium | Bookmarked |
| 21 | Stringoholics | Java | O(nm, nmaxNum) | O(n+m) n is input array length, m is average size of each string | HARD | Bookmarked, Covers many concepts - KMP, LCM |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | Min XOR Value | Java | O(nlogn) | O(1) | Easy | Bookmarked |
| 2 | Single Number | Java | O(n) | O(1) | Easy | |
| 3 | Number of 1 Bits | Java | O(1) | O(1) | Easy | Bookmarked, 2nd Solution with bits trick |
| 4 | Reverse Bits | Java | O(1) | O(1) | Easy | Bookmarked, 2nd Solution |
| 5 | Single Number II | Java | O(n) | O(1) | Medium | Bookmarked, 3x+1 |
| 6 | Divide Integers | Java | O(log(dividend)) | O(1) | Medium | Bookmarked, 1 approach is to subtract divisor, but takes O(dividend) time |
| 7 | Different Bits Sum Pairwise | Java | O(n) | O(1) | Medium | Bookmarked |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | Merge Two Sorted Lists II | Java | O(n+m) | O(1) | Easy | |
| 2 | Intersection Of Sorted Arrays | Java | O(n+m) | O(1) | Easy | |
| 3 | Minimize the absolute difference | Java | O(maxArrayLength) | O(1) | Easy | Bookmarked, Abs diff can be minimized either decreasing max element or increasing min element |
| 4 | Remove Duplicates from Sorted Array | Java | O(n) | O(1) | Easy | Bookmarked, Removing Element increases complexity, just set elements with 2nd pointer |
| 5 | Remove Duplicates from Sorted Array 2 | Java | O(n) | O(1) | Easy | Bookmarked |
| 6 | Remove Element from Array | Java | O(n) | O(1) | Easy | |
| 6 | Remove Element from Array | Java | O(n) | O(1) | Easy | |
| 7 | Sort by Color | Java | O(n) | O(1) | Easy | |
| 8 | Diffk | Java | O(n) | O(1) | Easy | Bookmarked, Start both pointers from 0 and not from opp. extreme ends |
| 9 | 3 Sum | Java | O(n^2 + nlogn) | O(1) | Easy | Bookmarked |
| 10 | 3 Sum Zero | Java | O(n^2 + nlogn) | O(1) | Medium | Bookmarked, Handle Duplicates |
| 11 | Max Continuous Series of 1s | Java | O(n) | O(1) | Medium | Bookmarked, Keeping window size having zeroes <= B |
| 12 | Array 3 Pointers | Java | O(maxArrayLength) | O(1) | Medium | Bookmarked, Abs diff can be minimized either decreasing max element or increasing min element |
| 13 | Counting Triangles | Java | O(n^2) | O(1) | Medium | Bookmarked, (A+B) > C by sorting the array |
| 14 | Container With Most Water | Java | O(n) | O(1) | Medium | Bookmarked |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | Intersection of Linked Lists | Java | O(n+m) | O(1) | Easy | |
| 2 | Reverse Linked List | Java | O(n) | O(1) | Easy | |
| 3 | Palindrome List | Java | O(n) | O(n) | Easy | Use Stack or reverse half linked list |
| 4 | Remove Duplicates from Sorted List | Java | O(n) | O(1) | Easy | |
| 5 | Remove Duplicates from Sorted List 2 | Java | O(n) | O(1) | Easy | |
| 6 | Merge Two Sorted Lists | Java | O(n) | O(1) | Easy | |
| 6 | Merge Two Sorted Lists | Java | O(n) | O(1) | Easy | |
| 7 | Remove Nth Node from List End | Java | O(n) | O(1) | Easy | |
| 8 | Rotate List | Java | O(n) | O(1) | Easy | |
| 9 | Reverse Lists 2 | Java | O(n) | O(1) | Easy | Bookmarked |
| 10 | Reorder List | Java | O(n) | O(1) | Medium | Bookmarked, Reverse Half and merge alternate |
| 11 | Swap List Nodes in pairs | Java | O(n) | O(1) | Medium | |
| 12 | K reverse linked list | Java | O(n) | O(1) | Medium | |
| 13 | Add Two Numbers as Lists | Java | O(n) | O(1) | Easy | |
| 14 | List Cycle | Java | O(n) | O(1) | Medium | Bookmarked |
| 15 | Partition List | Java | O(n) | O(1) | Easy | |
| 16 | Sort List | Java | O(nlogn) | O(1) | Medium |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | Simplify Directory Path | Java | O(n) | O(n) | Easy | |
| 2 | Redundant Braces | Java | O(n) | O(n) | Easy | |
| 3 | Nearest Smaller Element | Java | O(n) | O(n) | Easy | |
| 4 | Evaluate Expression | Java | O(n) | O(n) | Easy | |
| 5 | Min Stack | Java | O(1) | O(1) | Easy | Bookmarked, Doing Min in O(1) space is good one |
| 6 | Largest Rectangle in Histogram | Java | O(n) | O(n) | Medium | Bookmarked, Do read brute force and think in terms of stack |
| 7 | Rain Water Trapped | Java | O(n) | O(n) | Medium | Bookmarked |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | Sliding Window Maximum | Java | O(n) | O(n) | Medium | Bookmarked, Finding Min is reverse of current logic |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | ReverseLinkedList | Java | O(n) | O(n) | Easy | Bookmarked |
| 2 | Modular Expression | Java | O(log(power)) | O(1) | Easy | Bookmarked, Modular Exponentiation |
| 3 | Subset | Java | O(2^n) | O(n) | Easy | Bookmarked, Backtracking general algo |
| 4 | Combinations | Java | O(nCk) | O(n) | Easy | Bookmarked, Backtracking general algo |
| 5 | Combination Sum | Java | O(2^n) | O(targetSum) | Easy | Bookmarked, Backtracking general algo, Use Map for checking duplicates |
| 6 | Combination Sum 2 | Java | O(2^n) | O(targetSum) | Easy | |
| 7 | SubSets 2 | Java | O(2^n) | O(n) | Easy | Bookmarked, Either use hashmap or skip continuous elements in recursion function |
| 8 | Letter Phone | Java | O(3^n) | O(n) | Easy | |
| 9 | Palindrome Partitioning | Java | O(2^n) | O(n) | Easy | Bookmarked, can maintain 2-D array to keep true/false whether start-end is palindrome or not (DP) |
| 10 | Generate all Parentheses II | Java | O(2^n) | O(2n) | Easy | |
| 11 | Permutations | Java | O(n!) | O(n) | Medium | Bookmarked, Either use visited array or remove integer from input array then add back while backtracking |
| 12 | Gray Code | Java | O(2^n) | O(n) | Medium | Bookmarked, Other Solution of using reverse of (N-1) and prefixing 1 is good |
| 13 | Kth Permutation Sequence | Java | O(nk) | O(n) | Medium | Bookmarked, Use Maths plus recursion, first digit = k/(n-1)!+1 |
| 14 | NQueens | Java | O(n*n) | O(n) | Medium | Bookmarked |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | Colorful Number | Java | O(n*n) | O(n) | Easy | |
| 2 | Largest Continuous Sequence Zero Sum | Java | O(n) | O(n) | Easy | Bookmarked, 3 conditions - element 0, sum 0 or sum repeated |
| 3 | 2 Sum | Java | O(n) | O(1) | Easy | |
| 4 | 4 Sum | Java | O(n*n+nlogn) | O(n) | Medium | Bookmarked, Either use n^3 solution using 2 pointers and hashSet for unique sets or or use customised sorting plus hashSet |
| 5 | Valid Sudoku | Java | O(n*n) | O(n*n) | Medium | Bookmarked, check row, col and box, keep different maps |
| 6 | Diffk II | Java | O(n) | O(n) | Easy | |
| 7 | Anagrams | Java | O(n*m) , where m = average length of string | O(n) | Medium | Bookmarked, Good Concept |
| 8 | Equal | Java | O(n*n) | O(n) | Medium | Bookmarked |
| 9 | Copy List | Java | O(n) | O(n) | Medium | |
| 10 | Longest Substring Without Repeat | Java | O(n) | O(n) | Medium | Bookmarked |
| 11 | Window String | Java | O(n) | O(n) | Medium | Bookmarked, Use 2 pointers and map to keep count of characters included - plus and minus |
| 12 | Fraction | Java | O(n) | O(n) | Medium | Bookmarked |
| 13 | Points on the Straight Line | Java | O(n*n) | O(n) | Medium | Bookmarked, Slope should be same, Consider first point as start and rest as end and create map and repeat; Keep edge cases like which slopes are valid and others keep in diff variables |
| 14 | Substring Concatenation | Java | O(n*n) | O(n) | Medium | Bookmarked, Brute force but just using hashmap for string match |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | N max pair combinations | Java | O(nlogn) | O(n) | Medium | Bookmarked, Create a min heap and loop through n^2 pairs |
| 2 | Magician and Chocolates | Java | O(klogn) | O(n) | Easy | |
| 3 | Merge K Sorted Lists | Java | O(Nlogk), where k = initial lists and N = total sum of nodes from all lists | O(k) | Medium |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | Distinct Numbers in Window | Java | O(n) | O(n) | Easy | |
| 2 | LRU | Java | O(1) for get and O(n) for set | O(n) | Easy | |
| 3 | Ways to form Max Heap | Java | O(log2n^2) | O(log2n) | Hard | Bookmarked, T(n) = n-1Cl*T(l)*T(r), where r = n-1-l |
| Id | Title | Solution | Time | Space | Difficulty | Note |
|---|---|---|---|---|---|---|
| 1 | Valid Binary Search Tree | Java | O(n) | O(log2n) | Easy | |
| 2 | Next Greater Number BST | Java | O(logn) | O(1) | Easy | Bookmarked, Good Question plus also know inorder using 1 stack |
| 3 | Max Depth of Binary Tree | Java | O(n) | O(n) | Easy | |
| 4 | Vertical Order traversal of Binary Tree | Java | O(n) | O(n) | Easy | |
| 5 | Inorder Traversal | Java | O(n) | O(n) | Easy | Bookmarked |
| 6 | PreOrder Traversal | Java | O(n) | O(n) | Easy | Bookmarked |
| 6 | PreOrder Traversal | Java | O(n) | O(n) | Easy | Bookmarked |
| 7 | PostOrder Traversal | Java | O(n) | O(n) | Medium | Bookmarked, Using 2 stacks is easy |
| 8 | Hotel Reviews | Java | O(Sum of all input strings length) | O(n) | Medium | Bookmarked, Use tries or Hashset |
| 9 | Balanced Binary Tree | Java | O(n) | O(n) | Easy | |
| 10 | Identical Binary Trees | Java | O(n) | O(n) | Easy | |
| 11 | Symmetric Binary Tree | Java | O(n) | O(n) | Easy | |
| 12 | Inorder Traversal of Cartesian Tree | Java | O(n) | O(n) | Easy | |
| 13 | Sorted Array To Balanced BST | Java | O(n) | O(n) | Easy | |
| 14 | Binary Tree From Inorder And Postorder | Java | O(n) | O(n) | Easy | Bookmarked |
| 15 | Construct Binary Tree From Inorder And Preorder | Java | O(n) | O(n) | Easy | |
| 16 | Kth Smallest Element In Tree | Java | O(n) | O(n) | Easy | Bookmarked, Can be done without extra space as well |
| 17 | 2-Sum Binary Tree | Java | O(n) | O(logn) | Medium | Bookmarked, Can be done in O(n) space with sorted array |
| 18 | BST Iterator | Java | O(1) | O(logn) | Easy | Bookmarked, Can be done in O(n) space with array |
| 19 | Recover Binary Search Tree | Java | O(n) | O(1) | Medium | Bookmarked; Morris Algo - attaching current to inorder predecessor, Can be done in O(n) space with array, rest concept is same |
| 20 | Invert the Binary Tree | Java | O(n) | O(n) | Easy | Bookmarked |
| 21 | ZigZag Level Order Traversal BT | Java | O(n) | O(n) | Easy | Can be solved using 2 stacks or queue |
| 22 | Min Depth of Binary Tree | Java | O(n) | O(n) | Easy | |
| 23 | Path Sum | Java | O(n) | O(n) | Easy | |
| 24 | Sum Root to Leaf Numbers | Java | O(n) | O(n) | Medium | Bookmarked, mod can be used even before number is formed |
| 25 | Root to Leaf Paths With Sum | Java | O(n) | O(n) | Medium | Bookmarked |
| 26 | Populate Next Right Pointers Tree | Java | O(n) | O(1) | Medium | Bookmarked, If Space was not constant then using queue is very easy |
| 27 | Least Common Ancestor | Java | O(n) | O(n) | Medium | Bookmarked |
| 28 | Shortest Unique Prefix | Java | O(n*m) | O(total unique characters) | Medium | Bookmarked, either use count of unique flag at each node, update the child's property and not current node |
| 29 | Flatten Binary Tree to Linked List | Java | O(n) | O(1) | Medium | Bookmarked, Can be solved using stack or recursion |
| 30 | Order of People Heights | Java | O(nlogn) | O(n) | Medium | Bookmarked, Solve it like a puzzle, good question |