Data Structures and Algorithms

  You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and   it will automatically contact the police if two adjacent houses were broken into on the same night . Given an integer array  nums  representing the amount of money of each house, return  the maximum amount of money you can rob tonight  without alerting the police .   Example 1: Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. Example 2: Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12. Answer: Think of the answer in terms of a decision tree. You can either start at position at index 0 or 1. Since ...

Algorithm: Initialize two pointers, left at the start and right at the end of the string. Iterate until the left pointer is before the right pointer, skipping non-alphanumeric characters for both pointers. Compare characters positioned at the left and right pointers in lowercase; if they differ, return FALSE. Move left forward and right backward to check the next pair of characters. If the traversal completes without mismatches, return TRUE indicating the string is a palindrome. valid palindrome

  The two pointers pattern is a versatile technique used in problem-solving to efficiently traverse or manipulate sequential data structures, such as arrays or linked lists.  As the name suggests, it involves maintaining two pointers that traverse the data structure in a coordinated manner, typically starting from diffrent positions or moving in opossite directions.  These pointers dynamically adjust based on specific conditions or criteria, allowing for the efficient exploration of the data and enabling solutions with optimal time and space complexity.  Whenever there’s a requirement to find two data elements in an array that satisfy a certain condition, the two pointers pattern should be the first strategy to come to mind. The pointers can be used to iterate through the data structure in one or both directions, depending on the problem statement.  Valid Palindrome For example, to identify whether a string is a palindrome, we can use one pointer to i...

  You are given an integer array   cost   where   cost[i]   is the cost of   i th   step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index  0 , or the step with index  1 . Return  the minimum cost to reach the top of the floor . Example 1: Input: cost = [10, 15 ,20] Output: 15 Explanation: You will start at index 1. - Pay 15 and climb two steps to reach the top. The total cost is 15. Example 2: Input: cost = [ 1 ,100, 1 ,1, 1 ,100, 1 , 1 ,100, 1 ] Output: 6 Explanation: You will start at index 0. - Pay 1 and climb two steps to reach index 2. - Pay 1 and climb two steps to reach index 4. - Pay 1 and climb two steps to reach index 6. - Pay 1 and climb one step to reach index 7. - Pay 1 and climb two steps to reach index 9. - Pay 1 and climb one step to reach the top. The total cost is 6.

You are climbing a staircase. It takes   n   steps to reach the top. Each time you can either climb  1  or  2  steps. In how many distinct ways can you climb to the top? Example 1: Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps  Example 2: Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step Hint: To reach nth step, what could have been your previous steps? (Think about the step sizes) Answer for n=5: Starting at  step 0 , you have  two choices  — move  1 step  (to step 1) or  2 steps  (to step 2). From  step 1 , you can move to  step 2  or  step 3 . From  step 2 , you can move to  step 3  or  step 4 . From  step 3 , you can move to  step 4  or  step 5 . From  step 4 , you can move to  step 5 ...

Understanding Dynamic Programming in Two Stages Dynamic programming (DP) is a way to solve complex problems by breaking them into smaller, overlapping subproblems. It is especially useful when the same subproblems are solved many times in a simple recursive solution. A good way to build a dynamic programming algorithm is to go through two main stages: Stage 1: Develop a Recursive Solution The first step is to describe the problem in terms of smaller versions of itself.  (a) Specification You must clearly define what your recursive function does. For example, for the Fibonacci sequence: Fibonacci series The Fibonacci sequence starts with 0 and 1, and every number after that is the sum of the previous two. (b) Recursive Formula Here is the recursive function written formally:This definition expresses the problem in terms of smaller subproblems: computing `F(n-1)` and `F(n-2)`. The recursive version is easy to understand but slow, because it repeats many calculations. Stage 2: Build t...