Striver's SDE Sheet – Top Coding Interview Problems

A comprehensive collection of 191 handpicked coding interview problems covering all major topics in Data Structures & Algorithms. These problems are frequently asked in coding interviews at top tech companies like Google, Amazon, Microsoft, Facebook, Swiggy, Flipkart, and many more.

Table of Contents

• Overview
• Topics Covered
• Problem List by Topic
• How to Use This Repository
• Problem Format
• Contributing

What this project does

This repository contains solutions to Striver's SDE Sheet problems, one of the most comprehensive and well-structured interview preparation resources. Each problem includes:

• Clean, well-documented Python solutions
• Time and Space Complexity analysis
• Problem descriptions and approaches
• Optimized solutions following best practices

Official Resources

• Official SDE Sheet: https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/

Topics Covered

1. Arrays & Mathematics (Problems 1-22)

• Matrix operations
• Sorting algorithms
• Two pointers technique
• Prefix sums and sliding window
• Mathematical computations

2. Linked Lists (Problems 25-38)

• Reversal operations
• Cycle detection
• Merging and intersections
• Advanced pointer manipulation

3. Greedy Algorithm (Problems 43-48)

• Activity selection
• Interval problems
• Knapsack variants
• Coin change problems

4. Recursion & Backtracking (Problems 49-60)

• Subset generation
• Permutation problems
• N-Queens and Sudoku
• Maze problems

5. Binary Search (Problems 61-68)

• Search in sorted/rotated arrays
• Median problems
• Allocation problems
• Advanced binary search applications

6. Heaps (Problems 69-74)

• Min/Max heap implementation
• K-th largest/smallest elements
• Merge sorted arrays
• Frequency-based problems

7. Stacks & Queues (Problems 75-91)

• Stack/Queue implementations
• Monotonic stack problems
• LRU/LFU cache
• Sliding window maximum

8. String Algorithms (Problems 92-103)

• String manipulation
• Pattern matching (KMP, Rabin-Karp, Z-function)
• Palindrome problems
• String parsing

9. Binary Trees (Problems 104-131)

• Tree traversals (Inorder, Preorder, Postorder, Level-order)
• Tree views (Top, Bottom, Left, Right)
• Tree construction
• Tree properties and validations

10. Binary Search Trees (Problems 132-148)

• BST operations
• LCA in BST
• K-th element problems
• BST iterator

11. Graphs (Problems 151-169)

• DFS and BFS
• Cycle detection
• Topological sort
• Shortest path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)
• MST algorithms (Prim's, Kruskal's)
• Strongly Connected Components

12. Dynamic Programming (Problems 170-184)

• 1D DP problems
• 2D DP problems
• LIS, LCS
• Knapsack variants
• MCM (Matrix Chain Multiplication)
• Edit distance

13. Tries (Problems 185-191)

• Trie implementation
• Prefix matching
• XOR problems
• String manipulation with Tries

Problem List by Topic

Arrays & Mathematics (1-22)

#	Problem	File
1	Set Matrix Zeros	001_set_matrix_zeros.py
2	Pascal's Triangle	002_pascals_triangle.py
3	Next Permutation	003_next_permutation.py
4	Kadane's Algorithm	004_kadanes_algorithm.py
5	Sort an Array of 0s, 1s, and 2s	005_sort_an_array_of_0s_1s_and_2s.py
6	Stock Buy and Sell	006_stock_buy_and_sell.py
7	Rotate Matrix	007_rotate_matrix.py
8	Merge Overlapping Subintervals	008_merge_overlapping_subintervals.py
9	Merge Two Sorted Arrays Without Extra Space	009_merge_two_sorted_arrays_without_extra_space.py
10	Find the Duplicate in an Array of N+1 Integers	010_find_the_duplicate_in_an_array_of_n1_integers.py
11	Repeat and Missing Number	011_repeat_and_missing_number.py
12	Inversion of Array (Pre-req: Merge Sort)	012_inversion_of_array_pre-req_merge_sort.py
13	Search in a 2D Matrix	013_search_in_a_2_d_matrix.py
14	Pow(x, n)	014_powx_n.py
15	Majority Element (>N/2 times)	015_majority_element_n2_times.py
16	Majority Element (>N/3 times)	016_majority_element_n3_times.py
17	Grid Unique Paths	017_grid_unique_paths.py
18	Reverse Pairs	018_reverse_pairs_leetcode.py
19	2Sum Problem	019_2sum_problem.py
20	4-Sum Problem	020_4-sum_problem.py
21	Longest Consecutive Sequence	021_longest_consecutive_sequence.py
22	Largest Subarray with K Sum	022_largest_subarray_with_k_sum.py
23	Count Number of Subarrays with Given XOR K	023_count_number_of_subarrays_with_given_xor_k.py
24	Longest Substring Without Repeat	024_longest_substring_without_repeat.py

Linked Lists (25-38)

#	Problem	File
25	Reverse a Linked List	025_reverse_a_linkedlist.py
26	Find the Middle of Linked List	026_find_the_middle_of_linkedlist.py
27	Merge Two Sorted Linked List	027_merge_two_sorted_linked_list_use_method_used_in_mergesort.py
28	Remove N-th Node from Back of Linked List	028_remove_n-th_node_from_back_of_linkedlist.py
29	Add Two Numbers as Linked List	029_add_two_numbers_as_linkedlist.py
30	Delete a Given Node When a Node is Given (0(1) Solution)	030_delete_a_given_node_when_a_node_is_given01_solution.py
31	Find Intersection Point of Y Linked List	031_find_intersection_point_of_y_linkedlist.py
32	Detect a Cycle in Linked List	032_detect_a_cycle_in_linked_list.py
33	Reverse a Linked List in Groups of Size K	033_reverse_a_linkedlist_in_groups_of_size_k.py
34	Check if a Linked List is Palindrome or Not	034_check_if_a_linkedlist_is_palindrome_or_not.py
35	Find the Starting Point of the Loop of Linked List	035_find_the_starting_point_of_the_loop_of_linkedlist.py
36	Flattening of a Linked List	036_flattening_of_a_linkedlist.py
37	Rotate a Linked List	037_rotate_a_linkedlist.py
38	Clone a Linked List with Random and Next Pointer	038_clone_a_linked_list_with_random_and_next_pointer.py

Arrays Continued (39-42)

#	Problem	File
39	3 Sum	039_3_sum.py
40	Trapping Rainwater	040_trapping_rainwater.py
41	Remove Duplicate from Sorted Array	041_remove_duplicate_from_sorted_array.py
42	Max Consecutive Ones	042_max_consecutive_ones.py

Greedy Algorithm (43-48)

#	Problem	File
43	N Meetings in One Room	043_n_meetings_in_one_room.py
44	Minimum Number of Platforms Required for a Railway	044_minimum_number_of_platforms_required_for_a_railway.py
45	Job Sequencing Problem	045_job_sequencing_problem.py
46	Fractional Knapsack Problem	046_fractional_knapsack_problem.py
47	Greedy Algorithm to Find Minimum Number of Coins	047_greedy_algorithm_to_find_minimum_number_of_coins.py
48	Assign Cookies	048_assign_cookies.py

Recursion & Backtracking (49-60)

#	Problem	File
49	Subset Sums	049_subset_sums.py
50	Subset-II	050_subset-ii.py
51	Combination Sum-1	051_combination_sum-1.py
52	Combination Sum-2	052_combination_sum-2.py
53	Palindrome Partitioning	053_palindrome_partitioning.py
54	K-th Permutation Sequence	054_k-th_permutation_sequence.py
55	Print All Permutations of a String/Array	055_print_all_permutations_of_a_stringarray.py
56	N Queens Problem	056_n_queens_problem.py
57	Sudoku Solver	057_sudoko_solver.py
58	M Coloring Problem	058_m_coloring_problem.py
59	Rat in a Maze	059_rat_in_a_maze.py
60	Word Break (Print All Ways)	060_word_break_print_all_ways.py

Binary Search (61-68)

#	Problem	File
61	The N-th Root of an Integer	061_the_n-th_root_of_an_integer.py
62	Matrix Median	062_matrix_median.py
63	Find the Element That Appears Once in a Sorted Array	063_find_the_element_that_appears_once_in_a_sorted_array_and_the_rest_element_appears_twice_binary_search.py
64	Search Element in a Sorted and Rotated Array	064_search_element_in_a_sorted_and_rotated_array_find_pivot_where_it_is_rotated.py
65	Median of 2 Sorted Arrays	065_median_of_2_sorted_arrays.py
66	K-th Element of Two Sorted Arrays	066_k-th_element_of_two_sorted_arrays.py
67	Allocate Minimum Number of Pages	067_allocate_minimum_number_of_pages.py
68	Aggressive Cows	068_aggressive_cows.py

Heaps (69-74)

#	Problem	File
69	Max Heap / Min Heap Implementation	069_max_heap_min_heap_implementation_only_for_interviews.py
70	Kth Largest Element	070_kth_largest_element.py
71	Maximum Sum Combination	071_maximum_sum_combination.py
72	Find Median from Data Stream	072_find_median_from_data_stream.py
73	Merge K Sorted Arrays	073_merge_k_sorted_arrays.py
74	K Most Frequent Elements	074_k_most_frequent_elements.py

Stacks & Queues (75-91)

#	Problem	File
75	Implement Stack Using Arrays	075_implement_stack_using_arrays.py
76	Implement Queue Using Arrays	076_implement_queue_using_arrays.py
77	Implement Stack Using Queue (Using Single Queue)	077_implement_stack_using_queue_using_single_queue.py
78	Implement Queue Using Stack (01 Amortized Method)	078_implement_queue_using_stack_01_amortized_method.py
79	Check for Balanced Parentheses	079_check_for_balanced_parentheses.py
80	Next Greater Element	080_next_greater_element.py
81	Sort a Stack	081_sort_a_stack.py
82	Next Smaller Element	082_next_smaller_element.py
83	LRU Cache (Important)	083_lru_cache_important.py
84	LFU Cache	084_lfu_cache.py
85	Largest Rectangle in a Histogram	085_largest_rectangle_in_a_histogram.py
86	Sliding Window Maximum	086_sliding_window_maximum.py
87	Implement Min Stack	087_implement_min_stack.py
88	Rotten Orange (Using BFS)	088_rotten_orange_using_bfs.py
89	Stock Span Problem	089_stock_span_problem.py
90	Find the Maximum of Minimums of Every Window Size	090_find_the_maximum_of_minimums_of_every_window_size.py
91	The Celebrity Problem	091_the_celebrity_problem.py

String Algorithms (92-103)

#	Problem	File
92	Reverse Words in a String	092_reverse_words_in_a_string.py
93	Longest Palindrome in a String	093_longest_palindrome_in_a_string.py
94	Roman Number to Integer and Vice Versa	094_roman_number_to_integer_and_vice_versa.py
95	Implement Atoi/StrStr	095_implement_atoistrstr.py
96	Longest Common Prefix	096_longest_common_prefix.py
97	Rabin Karp	097_rabin_karp.py
98	Z-Function	098_z-function.py
99	KMP Algo / LPS(Pi) Array	099_kmp_algo__lpspi_array.py
100	Minimum Characters Needed to be Inserted in the Beginning to Make it Palindromic	100_minimum_characters_needed_to_be_inserted_in_the_beginning_to_make_it_palindromic.py
101	Check for Anagrams	101_check_for_anagrams.py
102	Count and Say	102_count_and_say.py
103	Compare Version Numbers	103_compare_version_numbers.py

Binary Trees (104-131)

#	Problem	File
104	Inorder Traversal	104_inorder_traversal.py
105	Preorder Traversal	105_preorder_traversal.py
106	Postorder Traversal	106_postorder_traversal.py
107	Morris Inorder Traversal	107_morris_inorder_traversal.py
108	Morris Preorder Traversal	108_morris_preorder_traversal.py
109	Left View of Binary Tree	109_leftview_of_binary_tree.py
110	Bottom View of Binary Tree	110_bottom_view_of_binary_tree.py
111	Top View of Binary Tree	111_top_view_of_binary_tree.py
112	Preorder Inorder Postorder in a Single Traversal	112_preorder_inorder_postorder_in_a_single_traversal.py
113	Vertical Order Traversal	113_vertical_order_traversal.py
114	Root to Node Path in Binary Tree	114_root_to_node_path_in_binary_tree.py
115	Max Width of a Binary Tree	115_max_width_of_a_binary_tree.py
116	Level Order Traversal / Level Order Traversal in Spiral Form	116_level_order_traversal__level_order_traversal_in_spiral_form.py
117	Height of a Binary Tree	117_height_of_a_binary_tree.py
118	Diameter of Binary Tree	118_diameter_of_binary_tree.py
119	Check if the Binary Tree is Height-Balanced or Not	119_check_if_the_binary_tree_is_height-balanced_or_not.py
120	LCA in Binary Tree	120_lca_in_binary_tree.py
121	Check if Two Trees are Identical or Not	121_check_if_two_trees_are_identical_or_not.py
122	Zig Zag Traversal of Binary Tree	122_zig_zag_traversal_of_binary_tree.py
123	Boundary Traversal of Binary Tree	123_boundary_traversal_of_binary_tree.py
124	Maximum Path Sum	124_maximum_path_sum.py
125	Construct Binary Tree from Inorder and Preorder	125_construct_binary_tree_from_inorder_and_preorder.py
126	Construct Binary Tree from Inorder and Postorder	126_construct_binary_tree_from_inorder_and_postorder.py
127	Symmetric Binary Tree	127_symmetric_binary_tree.py
128	Flatten Binary Tree to Linked List	128_flatten_binary_tree_to_linkedlist.py
129	Check if Binary Tree is the Mirror of Itself or Not	129_check_if_binary_tree_is_the_mirror_of_itself_or_not.py
130	Check for Children Sum Property	130_check_for_children_sum_property.py
131	Populate Next Right Pointers of Tree	131_populate_next_right_pointers_of_tree.py

Binary Search Trees (132-148)

#	Problem	File
132	Search Given Key in BST	132_search_given_key_in_bst.py
133	Construct BST from Given Keys	133_construct_bst_from_given_keys.py
134	Construct a BST from a Preorder Traversal	134_construct_a_bst_from_a_preorder_traversal.py
135	Check is a BT is BST or Not	135_check_is_a_bt_is_bst_or_not.py
136	Find LCA of Two Nodes in BST	136_find_lca_of_two_nodes_in_bst.py
137	Find the Inorder Predecessor/Successor of a Given Key in BST	137_find_the_inorder_predecessorsuccessor_of_a_given_key_in_bst.py
138	Floor in a BST	138_floor_in_a_bst.py
139	Ceil in a BST	139_ceil_in_a_bst.py
140	Find K-th Smallest Element in BST	140_find_k-th_smallest_element_in_bst.py
141	Find K-th Largest Element in BST	141_find_k-th_largest_element_in_bst.py
142	Find a Pair with a Given Sum in BST	142_find_a_pair_with_a_given_sum_in_bst.py
143	BST Iterator	143_bst_iterator.py
144	Size of the Largest BST in a Binary Tree	144_size_of_the_largest_bst_in_a_binary_tree.py
145	Serialize and Deserialize Binary Tree	145_serialize_and_deserialize_binary_tree.py
146	Binary Tree to Double Linked List	146_binary_tree_to_double_linked_list.py
147	Find Median in a Stream of Running Integers	147_find_median_in_a_stream_of_running_integers.py
148	K-th Largest Element in a Stream	148_k-th_largest_element_in_a_stream.py
149	Distinct Numbers in Window	149_distinct_numbers_in_window.py
150	K-th Largest Element in an Unsorted Array	150_k-th_largest_element_in_an_unsorted_array.py

Graphs (151-169)

#	Problem	File
151	Flood Fill Algorithm	151_flood-fill_algorithm.py
152	Clone a Graph (Not That Easy as It Looks)	152_clone_a_graph_not_that_easy_as_it_looks.py
153	DFS	153_dfs.py
154	BFS	154_bfs.py
155	Detect a Cycle in Undirected Graph (Using BFS)	155_detect_a_cycle_in_undirected_graph_using_bfs.py
156	Detect a Cycle in Undirected Graph (Using DFS)	156_detect_a_cycle_in_undirected_graph_using_dfs.py
157	Detect a Cycle in a Directed Graph (Using DFS)	157_detect_a_cycle_in_a_directed_graph_using_dfs.py
158	Detect a Cycle in a Directed Graph (Using BFS)	158_detect_a_cycle_in_a_directed_graph_using_bfs.py
159	Topological Sort (BFS)	159_topological_sort_bfs.py
160	Topological Sort (DFS)	160_topological_sort_dfs.py
161	Number of Islands (Do in Grid and Graph Both)	161_number_of_islandsdo_in_grid_and_graph_both.py
162	Bipartite Check (Using BFS)	162_bipartite_check_using_bfs.py
163	Bipartite Check (Using DFS)	163_bipartite_check_using_dfs.py
164	Strongly Connected Component (Using Kosaraju's Algo)	164_strongly_connected_componentusing_kosarajus_algo.py
165	Dijkstra's Algorithm	165_dijkstras_algorithm.py
166	Bellman-Ford Algo	166_bellman-ford_algo.py
167	Floyd Warshall Algorithm	167_floyd_warshall_algorithm.py
168	MST Using Prim's Algo	168_mst_using_prims_algo.py
169	MST Using Kruskal's Algo	169_mst_using_kruskals_algo.py

Dynamic Programming (170-184)

#	Problem	File
170	Max Product Subarray	170_max_product_subarray.py
171	Longest Increasing Subsequence	171_longest_increasing_subsequence.py
172	Longest Common Subsequence	172_longest_common_subsequence.py
173	0-1 Knapsack	173_0-1_knapsack.py
174	Edit Distance	174_edit_distance.py
175	Maximum Sum Increasing Subsequence	175_maximum_sum_increasing_subsequence.py
176	Matrix Chain Multiplication	176_matrix_chain_multiplication.py
177	Minimum Sum Path in the Matrix, Count Paths and Similar Type	177_minimum_sum_path_in_the_matrix_count_paths_and_similar_type_do_also_backtrack_to_find_the_minimum_path.py
178	Coin Change	178_coin_change.py
179	Subset Sum	179_subset_sum.py
180	Rod Cutting	180_rod_cutting.py
181	Egg Dropping	181_egg_dropping.py
182	Word Break	182_word_break.py
183	Palindrome Partitioning (MCM Variation)	183_palindrome_partitioning_mcm_variation.py
184	Maximum Profit in Job Scheduling	184_maximum_profit_in_job_scheduling.py

Tries (185-191)

#	Problem	File
185	Implement Trie (Prefix Tree)	185_implement_trie_prefix_tree.py
186	Implement Trie - 2 (Prefix Tree)	186_implement_trie_-_2_prefix_tree.py
187	Longest String with All Prefixes	187_longest_string_with_all_prefixes.py
188	Number of Distinct Substrings in a String	188_number_of_distinct_substrings_in_a_string.py
189	Power Set (This is Very Important)	189_power_set_this_is_very_important.py
190	Maximum XOR of Two Numbers in an Array	190_maximum_xor_of_two_numbers_in_an_array.py
191	Maximum XOR with an Element from Array	191_maximum_xor_with_an_element_from_array.py

How to Use This Repository

Prerequisites

• Python 3.x installed on your system
• Basic understanding of Data Structures and Algorithms

Getting Started

1. Clone the repository:

   git clone https://github.com/Tuhin-SnapD/Striver23-DSA
   cd done
   

2. Navigate to a specific problem: Each problem is in its own file, named descriptively. For example:

   python 019_2sum_problem.py
   

3. Study the solutions:

   • Read the problem description at the top of each file
   • Understand the approach and algorithm
   • Check the time and space complexity
   • Run the code and test with different inputs

Problem Format

Each solution file follows a consistent format:

"""
Problem Title

Brief problem description.

Time Complexity: O(...)
Space Complexity: O(...)
"""

# Import statements

# Solution code with detailed docstrings

Key Concepts Covered

• Time Complexity Analysis: Understanding Big-O notation
• Space Optimization: Reducing memory usage
• Algorithm Design: Choosing the right approach
• Edge Case Handling: reliable solutions
• Code Quality: Clean, readable, and maintainable code

Tips for Interview Preparation

1. Understand, Don't Memorize: Focus on understanding the pattern and approach
2. Practice Daily: Consistency is key to mastering DSA
3. Draw and Visualize: Sketch out solutions before coding
4. Discuss Edge Cases: Always think about corner cases
5. Optimize Incrementally: Start with brute force, then optimize
6. Mock Interviews: Practice explaining your solutions aloud

Contributing

Contributions are welcome! If you find any issues or want to improve solutions:

1. Fork the repository
2. Create a feature branch
3. Make your changes
4. Submit a pull request

License

This project is licensed under the MIT License.

Acknowledgments

• Striver for creating the comprehensive SDE Sheet
• Original sheet available at: takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/
• Original repository: github.com/Tuhin-SnapD/Striver23-DSA
• All contributors who helped improve this repository

Useful Resources

• LeetCode - Practice platform
• GeeksforGeeks - DSA tutorials
• HackerRank - Coding challenges
• InterviewBit - Interview preparation

---

**Happy Coding! **

Remember: The goal is not just to solve problems, but to understand the underlying concepts and patterns that will help you tackle new challenges in interviews and real-world scenarios.