Complete DSA C++ Notes

This repository contains various programs organized by topics. Below is a list of topics and corresponding files for each section.

---

Table of Contents

1. Basics
2. STL
3. Basic Maths
4. Recursion
5. Hashing & Maps
6. Sorting Techniques
7. Arrays
8. Binary Search
9. Strings
10. Linked List
11. Stack and Queue

---

Basics

This folder covers the fundamental concepts of programming.

• 01_basics.cpp: Introduction to basic syntax and structure in C++.
• 02_functions.cpp: Functions and their usage in C++.
• 03_complexity.cpp: Understanding time and space complexity.
• 04_patterns.cpp: Patterns and loops used in problem-solving.

---

STL (Standard Template Library)

Programs related to the Standard Template Library (STL) in C++.

• 05.1_pairs.cpp: Working with pairs in STL.
• 05.2_vectors.cpp: Introduction to vectors in STL.
• 05.3_lists.cpp: Usage of lists in STL.
• 05.4_DQ.cpp: Working with deque in STL.
• 05.5_stack.cpp: Stack implementation in STL.
• 05.6_queue.cpp: Queue implementation in STL.
• 05.7_priorityQueue.cpp: Priority Queue in STL.
• 05.8_sets.cpp: Using sets in STL.
• 05.9_maps.cpp: Maps and unordered maps in STL.
• 05.10_impAlgs.cpp: Important STL algorithms.

---

Basic Maths

This folder contains basic mathematical concepts implemented in C++.

• 01_extractDigits.cpp: Extracting digits from a number.
• 02_pallin&armst.cpp: Palindrome and Armstrong numbers.
• 03_noOfDivisions.cpp: Counting number of divisions.
• 04_primeNo.cpp: Prime number check.
• 05_gcdHcf.cpp: Calculating GCD and HCF.

---

Recursion

Programs demonstrating the power of recursion.

• 01_recursion_basics.cpp: Introduction to recursion.
• 02_problems_recursion.cpp: Recursion problems.
• 03_parameterized_recursion.cpp: Parameterized recursion.
• 04_functional_recursion.cpp: Functional recursion.
• 05_multiple_recursion_calls.cpp: Multiple recursive calls.

---

Hashing & Maps

Hashing techniques and map implementations in C++.

• 01_introduction.cpp: Introduction to hashing.
• 02_Hashing_in_characters.cpp: Hashing techniques for characters.
• 03_map_and_unordered_map.cpp: Maps and unordered maps in C++.

---

Sorting Techniques

Implementation of various sorting algorithms.

• 01_selection_sort.cpp: Selection sort.
• 02_bubble_sort.cpp: Bubble sort.
• 03_insertion_sort.cpp: Insertion sort.
• 04_merge_sort.cpp: Merge sort.
• 05_quick_sort.cpp: Quick sort.
• 06_recursive_insertion_bubble.cpp: Recursive implementation of insertion and bubble sort.

---

Arrays in C++

Basic Array Operations

• 01_basics_of_arrays.cpp: Introduction to arrays in C++.
• 02_largest_element.cpp: Finding the largest element in an array.
• 03_second_largest_element.cpp: Finding the second largest element in an array.
• 04_check_if_array_sorted.cpp: Checking if the array is sorted.
• 05_remove_dupli_from_sorted.cpp: Removing duplicates from a sorted array.

Array Rotation and Manipulation

• 06_left_rotate_array_1.cpp: Left rotate an array by 1 position.
• 07_left_rotate_array_n.cpp: Left rotate an array by N positions.
• 08_move_zeros_to_end.cpp: Moving zeros to the end of an array.

Search Algorithms

• 09_linear_search.cpp: Linear search algorithm to find an element in an array.
• 10_union_of_sorted_arrays.cpp: Finding the union of two sorted arrays.
• 11_intersection_of_sorted_arrays.cpp: Finding the intersection of two sorted arrays.
• 12_find_missing_no_in_array.cpp: Finding the missing number in an array.

Special Problems and Techniques

• 13_maximum_consecutive_ones.cpp: Finding the maximum number of consecutive ones in a binary array.
• 14_number_appearing_once.cpp: Finding the element that appears only once in an array.
• 15_longest_subarray_given_sum.cpp: Finding the longest subarray with a given sum (considering both positive and negative elements).
• 16_two_sum_problem.cpp: Finding two numbers in an array that add up to a given sum.

Sorting and Rearrangement

• 17_sort_0s_1s_2s_array.cpp: Sorting an array containing only 0s, 1s, and 2s.
• 18_majority_element.cpp: Finding the majority element in an array (element that appears more than n/2 times).

Advanced Array Algorithms

• 19_kadanes_algo_max_subarray_sum.cpp: Implementing Kadane's Algorithm to find the maximum subarray sum.
• 20_dp_on_stocks.cpp: Dynamic programming approach to solving the Stock Buy-Sell Problem for maximum profit.

Array Rearrangement and Permutations

• 21_rearrange_elements_by_sign.cpp: Rearranging elements of an array by separating positive and negative numbers.
• 22_next_permutation.cpp: Finding the next lexicographical permutation of an array.
• 23_leaders_in_array.cpp: Finding the leaders in an array (elements greater than or equal to all elements to their right).

Sequence and Matrix Problems

• 24_longest_consecutive_seq.cpp: Finding the longest consecutive sequence in an array.
• 25_set_matrix_zeros.cpp: Setting matrix rows and columns to zero if an element is zero.
• 26_rotate_matrix.cpp: Rotating a matrix 90 degrees.
• 27_print_matrix_in_spiral.cpp: Printing a matrix in spiral order.

Subarray Problems

• 28_number_of_subarrays.cpp: Counting the number of subarrays.

---

Binary Search

This folder contains key Binary Search concepts and their C++ implementations:

Basic Problems

• 01_binary_search_basics.cpp: Basic binary search.
• 02_lower_bound.cpp: Finds the first insert position in a sorted array.
• 03_upper_bound.cpp: Finds the first element greater than the target.

Searching

• 04_search_insert_position.cpp: Finds the insert position of a target.
• 05_floor_and_ceil_in_array.cpp: Finds floor and ceil of a target element.
• 06_first_last_occurrence.cpp: Finds first and last occurrences of an element.
• 07_no_of_occurrences.cpp: Counts the number of occurrences of an element.
• 08_search_in_rotated_sorted_array.cpp: Searches in a rotated sorted array.
• 09_rotated_sorted_with_duplicates.cpp: Handles duplicates in rotated arrays.

Find element

• 10_min_in_rotated_sorted_subarray.cpp: Finds minimum in rotated array.
• 11_no_of_times_array_rotated.cpp: Counts array rotations.
• 12_single_ele_in_sorted_array.cpp: Finds single non-duplicate element in sorted array.
• 13_find_peak_element.cpp: Finds peak element (not smaller than neighbors).

Binary search on Answers

• 14_find_sqrt_of_integer.cpp: Finds integer square root.
• 15_nth_root_of_integer.cpp: Finds nth root of a number.
• 16_koka_eating_bananas.cpp: Uses binary search to minimize banana eating time.
• 17_min_days_to_make_bouquets.cpp: Finds minimum days to make bouquets.
• 18_find_smallest_divisor.cpp: Finds smallest divisor of a number.
• 19_capacity_ship_packages.cpp: Determines ship capacity for packages.
• 20_kth_missing_number.cpp: Finds the kth missing number.
• 21_find_row_with_max_1s.cpp: Finds row with maximum 1s in a binary matrix.
• 22_search_in_2D_matrix.cpp: Searches for an element in a 2D matrix.
• 23_search_row_col_wise_sorted_matrix.cpp: Searches in a row and column-wise sorted 2D matrix.

---

Strings

This folder contains key String Problems and their C++ implementations:

• 01_remove_outermost_parentheses.cpp: Removes the outermost parentheses from a string.
• 02_reverse_words_in_string.cpp: Reverses the words in a given string.
• 03_check_palindrome.cpp: Checks if a given string is a palindrome.
• 04_largest_odd_no_in_string.cpp: Finds the largest odd number present in a string.
• 05_longest_common_prefix.cpp: Finds the longest common prefix among a set of strings.
• 06_isomorphic_strings.cpp: Checks if two strings are isomorphic.
• 07_check_strings_rotations.cpp: Checks if one string is a rotation of another.
• 08_check_if_strings_are_anagram.cpp: Checks if two strings are anagrams of each other.
• 09_sort_chars_by_frequency.cpp: Sorts the characters in a string by their frequency of occurrence.
• 10_max_nesting_depth.cpp: Finds the maximum nesting depth of parentheses in a string.
• 11_integer_to_roman_versa.cpp: Converts an integer to its Roman numeral representation and vice versa.
• 12_implement_atoi.cpp: Implements the atoi function (string to integer conversion).
• 13_longest_palindromic_substring.cpp: Finds the longest palindromic substring within a given string.
• 14_sum_beauty_substring.cpp: Calculates the sum of beauty of all substrings in a string.

---

Here’s the properly formatted and structured version of your Linked List problems with the corresponding C++ implementations:

---

Linked List

This folder contains key Linked List problems and their corresponding C++ implementations.

1. 01_linked_list_basics.cpp: Implements the basics of linked lists.
2. 02_deletion_of_node_SLL.cpp: Demonstrates the deletion of a node in a Singly Linked List (SLL).
3. 03_insertion_of_node_SLL.cpp: Demonstrates the insertion of a node in a Singly Linked List (SLL).
4. 04_doubly_linked_list_basics.cpp: Implements the basics of Doubly Linked Lists (DLL).
5. 05_deletion_of_node_DLL.cpp: Demonstrates the deletion of a node in a Doubly Linked List (DLL).
6. 06_insertion_of_node_DLL.cpp: Demonstrates the insertion of a node in a Doubly Linked List (DLL).
7. 07_reverse_a_DLL.cpp: Demonstrates reversing a Doubly Linked List (DLL).
8. 08_add_two_nos_in_LL.cpp: Demonstrates adding two linked lists.
9. 09_group_odd_and_even.cpp: Demonstrates grouping the linked lists based on even and odd indexes.
10. 10_sort_LL_of_0s_1s_2s.cpp: Demonstrates sorting of linked lists with 0s, 1s, and 2s.
11. 11_remove_nth_node_from_end.cpp: Demonstrates removing the nth node from the end of the linked list.
12. 12_reverse_a_Linked_List.cpp: Demonstrates reversing a linked list.
13. 13_find_the_middle_of_LL.cpp: Demonstrates finding the middle of a linked list.
14. 14_check_if_LL_palindrome_or_not.cpp: Demonstrates checking if a linked list is a palindrome.
15. 15_adding_1_to_given_LL.cpp: Demonstrates adding 1 to a given linked list.
16. 16_intersection_pt_of_Y_LL.cpp: To find the intersection point of a Y Linked List.
17. 17_detect_a_loop_in_LL.cpp: To detect a loop/cycle in a Linked List.
18. 18_find_length_of_loop_in_LL.cpp: To find length of the loop in LL.
19. 19_delete_middle_node.cpp: To detect the middle node in LL.
20. 20_find_starting_point_of_loop.cpp: To find starting point of the loop/cycle in LL.
21. 21_merge_two_sorted_LL.cpp.cpp: To merge two sorted Linked Lists.
22. 22_sort_a_LL.cpp: To Sort a Linked List.
23. 23_del_occurences_of_key_in_DLL.cpp: Delete the occurrences of a key in a Doubly Linked List.
24. 24_find_pairs_with_given_sum_DLL.cpp: To find the pairs in DLL for the given sum.
25. 25_remove_dupli_from_sorted_DLL.cpp: Remove duplicate from the sorted Doubly Linked List (DLL)
26. 26_rotate_a_LL_k_times.cpp: Rotate a Linked List by k times.

---

Stack and Queue

1. intro_to_stack_and_queue.cpp: Introduction to Stacks and Queues — basic concepts and operations.
2. stack_queue_using_LL.cpp: Implement stack and queue using a linked list.
3. stack_and_queue_using_both.cpp: Implement stack and queue using both arrays and linked lists.
4. balanced_parentheses.cpp: Check if parentheses in an expression are balanced using a stack.
5. prefix_infix_postfix.cpp: Convert between prefix, infix, and postfix notation using stacks.
6. implement_min_stack.cpp: Implement a stack that supports the getMin() operation in constant time.
7. 07_next_greater_element.cpp: Find the next greater element in the given array (Monotonic stack).
8. 08_next_cir_greater_element.cpp: Find the next greater element in the given array using circular array.
9. 09_previous_smaller_element.cpp: Find the previous smaller element for all elements in the array.
10. 10_sum_of_subarray_mins.cpp: Find the sum of subarray minimums of the array.
11. 11_sum_of_subarray_ranges.cpp: Find the sum of subarray ranges (subarray_max - subarray_min) of the array.
12. 12_aestorid_collisions.cpp: Find the result array after the Asteroid Collisions.
13. 13_largest_rect_in_histogram.cpp: FInd the largest rectangle in Histogram.
14. 14_maximal_rectangle.cpp: FInd the maximal rectangle in a 2D Matrix.
15. 15_remove_k_digits.cpp: Remove k digits from the given string.
16. 16_stock_and_span_problem.cpp: Stock and span problem in stack.

---

How to Use

1. Clone the repository using the following command:

   git clone https://github.com/YashChavanWeb/DSA_Complete_Notes

2. Navigate to the folder of interest:

   cd Programs/<Folder_Name>

3. Compile and run the C++ files:

   g++ <filename.cpp> -o <output_name>
   ./<output_name>

4. Enjoy exploring the programs and learning the concepts!

---

Contributing

Feel free to fork the repository, make changes, and create a pull request if you have improvements or additional programs to share.