Programming

Overview It is not easy to summarize the pattern of Two Pointers, but most likely it is used for list and linked list and the required time complexity is O(N) - the underlying pattern allows us to use Two Pointers to go through the list once to get the results. Common usage: Linear Structure: Typically applied to a sorted array or linked list. Two pointers might move in the same direction or in opposite directions. Classic Patterns: a. Converging Pointers (often used in sorted arrays): - Start one pointer at the beginning (left) and another at the end (right). - Move them toward each other until they meet or until some condition is satisfied. - Example: Checking if a sorted array has two numbers that sum up to a target. b. Sliding Window: - Use two pointers to represent the start and end of a window, then “slide” the window through the array/sequence. - Example: Finding the longest substring without repeating characters. c. Fast and Slow Pointers (often used in linked lists): - One pointer moves twice (or more times) as fast as the other. - Useful for detecting cycles in a linked list (Floyd’s Cycle Detection Algorithm) or finding the middle element. Usage Scenarios: Finding a Pair with a Given Sum/Target: Given a sorted array, determine if there’s a pair that sums up to a target. Move the left and right pointers based on the sum comparison to the target. Removing Duplicates: Two pointers can be used to remove duplicates from a sorted array or linked list, with one pointer iterating through and another pointing to the last non-duplicate item. Palindrome Checking: To determine if a string or linked list is a palindrome, you can use two pointers moving from the two ends towards the center. Max/Min Subarray/Sublist: Using the sliding window variant, find the subarray with the maximum/minimum sum or other properties. Advantages: Efficiency: The two-pointer technique can sometimes convert a brute force solution with time complexity O(n^2) to a more efficient O(n) solution. Space: This method is in-place and typically uses O(1) extra space. Example Questions 88. Merge Sorted Array You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively. ...

Overview The Divide-n-Conquer strategy often employs recursion, as it relies on applying the same method to reduce the problem size by half and subsequently combining the outcomes for the ultimate solution. I view Divide-n-Conquer in a light similar to MapReduce, particularly when the task involves transformation. MapReduce breaks down a large problem into more manageable, independent sub-problems. Since each of these sub-problems operates autonomously, we can address them sequentially and still integrate their solutions. Key to this approach is ensuring the main problem can be independently segmented and the derived solutions can be seamlessly merged. ...

Overview In one word, binary search is to search for a target in a sorted array. The idea is to shrink the search space to empty. It must be sorted because we can be sure how to shrink the search space and we normally reduce the search space by half so the time complexity is O(logN) where N is the size of entire search space. One common problem to understand Binary Search is how to identify the boundary of the search space. ...

If you are not using Java or Intellij Idea for your project, you could stop reading. Couple months ago, I am very excited with WSL2 and it works perfectly for me to work on some Java projects in Intellij Idea. Somehow everything is upside down and obviously after some updates of windows though I still stick with win10. Long story short! Intellij Idea is really slow with WSL regarding the version. The indexing takes forever and it is not new as I found in this thread and this thread and the problem could be one of the following: ...