Array and Strings

This lists out the various questions needed to be solved in arrays :-

1. 3-SUM - Find all the triplets in an array that sum up to zero.

   1. Article - https://www.geeksforgeeks.org/find-triplets-array-whose-sum-equal-zero/
   2. LeetCode Solution - https://leetcode.com/problems/3sum/discuss/140004/C++-optimized-O(n2)-solution (Modified so that duplicate triplets are returned).

2. K-SUM - Find all triplets that sum up to a given value.

   1. Article - https://www.geeksforgeeks.org/find-a-triplet-that-sum-to-a-given-value/
   2. Similar as 3-SUM, just tweak 0 to be k.

3. 3-SUM CLOSEST - Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target.

   1. LeetCode Solution - https://leetcode.com/problems/3sum-closest/discuss/140006/C++-solution
   2. Modified 3-SUM question.

4. 4-SUM - Find four elements that sum to a given value

   1. Article - https://www.geeksforgeeks.org/?p=23327
   2. O(n^2logn) and O(n^2) solution - https://www.geeksforgeeks.org/find-four-elements-that-sum-to-a-given-value-set-2/

5. First Missing Positive - Given an unsorted array, find the smallest missing positive integer.

   1. Article - https://www.geeksforgeeks.org/find-the-smallest-positive-number-missing-from-an-unsorted-array/
   2. LeetCode solution - https://leetcode.com/problems/first-missing-positive/discuss/140326/C++-solution

6. Jump Game - Minimum no. of jumps required to reach the end of the array.

   1. Article - https://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/ (O(n^2) DP approach)
   2. Article - https://www.geeksforgeeks.org/minimum-number-jumps-reach-endset-2on-solution/ (O(n) solution)
   3. LeetCode solution - Gave TLE. working on it. (https://leetcode.com/problems/jump-game-ii/description/)

7. SPIRAL MATRIX - Consists of a number of questions on spiral matrix.

   1. Article - https://www.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/ (LeetCode 54)
   2. Article - https://www.geeksforgeeks.org/print-n-x-n-spiral-matrix-using-o1-extra-space/ (LeetCode 59)

8. Unique Paths - Consists of a number of DP questions.

   1. Article - https://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/ (LeetCode 62)
   2. Article - https://www.geeksforgeeks.org/print-all-possible-paths-from-top-left-to-bottom-right-of-a-mxn-matrix/
   3. Article - https://www.geeksforgeeks.org/unique-paths-in-a-grid-with-obstacles/ (LeetCode 63)

9. Min Cost Path - https://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/ (LeetCode 64)

10. Search A 2D Matrix - Write an efficient algorithm that searches for a value in an m x n matrix

    1. Article - https://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/
    2. LeetCode Solution - https://leetcode.com/problems/search-a-2d-matrix/discuss/140331/C++-O(n)-solution

11. Set Matrix Zeroes - https://leetcode.com/problems/set-matrix-zeroes/discuss/140332/C++-in-place-solution (My leetcode solution)

12. SUBSETS - Find all distinct subsets of a given set.

    0. Pre-requisites - https://www.geeksforgeeks.org/power-set/
    1. Article - https://www.geeksforgeeks.org/find-distinct-subsets-given-set/
    2. LeetCode solution - https://leetcode.com/problems/subsets/ (Read https://www.geeksforgeeks.org/converting-strings-numbers-cc/ before trying to solve the LeetCode problem).

13. Merge two sorted arrays - Here are some questions related to it. (Very Imp.)

    1. Article - https://www.geeksforgeeks.org/merge-two-sorted-arrays/ (O(n+m) time complexity with O(n+m) space.)
    2. Article - https://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-space/ (O(mn) T.C. with O(1) space.)
    3. Article - https://www.geeksforgeeks.org/efficiently-merging-two-sorted-arrays-with-o1-extra-space/
    4. LeetCode - https://leetcode.com/problems/merge-sorted-array/

14. Remove Duplicates in Sorted Array - Here are some questions related to it.

    1. Article - https://www.geeksforgeeks.org/remove-duplicates-sorted-array/ (LeetCode 26)
    2. Article - https://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/
    3. LeetCode Question - https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

15. Word Search - Here are some questions related to it.

    1. Article - https://www.geeksforgeeks.org/search-a-word-in-a-2d-grid-of-characters/
    2. Article - https://www.geeksforgeeks.org/find-all-occurrences-of-the-word-in-a-matrix/

16. Search an element in a rotated and sorted array - Very imp.

    1. Article - https://www.geeksforgeeks.org/binary-search/ (Pre-requisite)
    2. Article - https://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/ (LeetCode 33)
    3. LeetCode - https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/ (Handling duplicates, first remove duplicates from the array in-place, and then use the above method.)

17. Largest Rectangle in histogram - Hard and important.

    1. Pre-requisite - Segment Trees - https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/ && https://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/.
    2. Article - https://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/ (O(nlogn) solution)
    3. Article - https://www.geeksforgeeks.org/largest-rectangle-under-histogram/ (O(n) solution).
    4. LeetCode - https://leetcode.com/problems/largest-rectangle-in-histogram/description/

18. Trapping rainwater - Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

    1. Article - https://www.geeksforgeeks.org/trapping-rain-water/
    2. LeetCode 42 solution - https://leetcode.com/problems/trapping-rain-water/description/

19. Best Time To Buy and Sell Stock - All Cases. Refer GFG and leetcode.

20. Maximum Sum Contiguous Sub-Array - Implementation of Kadane's Algo (DP).

    1. Article - https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
    2. LeetCode - https://leetcode.com/problems/maximum-subarray/description/ ( I have a little bit twisted solution in my leetcode one, where max_ending_here is being compared with nums[i], not 0, to handle the case when all the numbers in the array are negative.)
    3. Article - https://www.geeksforgeeks.org/maximum-product-subarray/ (Maximum product subarray, a little bit different, and tough..!).
    4. LeetCode - https://leetcode.com/problems/maximum-product-subarray/description/ (Tweaked code, to handle all cases).

Others -

1. Two Sum
2. Find pairs whose sum is x
3. Leaders in An Array
4. Longest Palindromic Substring - DP solution
5. Longest Palindromic Substring - Constant Space Solution
6. Manacher's Algorithm - Linear Time Longest Palindromic Substring
7. Next greater number with same set of digits
8. Longest Common Prefix - Set 1, Set 2, Set 3, Set 4.
9. Find the element that appears once.
10. Minimum element in a rotated and sorted array
11. Nth element in a set formed by two arrays
12. Row with the maximum no. of 1's
13. Two non-repeating elements in an array of repeating elements
14. Generate n-bit binary gray codes