## Dynamic Programming

Definition Dynamic Programming is a very powerful programming paradigm that can be employed to find optimal solutions to problems that possess the following properties: overlapping subproblems and optimal substructure. Overlapping subproblems A problem can be decomposed into smaller subproblems than can be reused multiple time to construct the overall solution The solutions to subproblems are often memoized to avoid re-work and improve time complexity Solutions to subproblems are reused more than once by subsequent solutions Optimal substructure The optimal solution to a problem can be constructed from the optimal solution of overlapping subproblems....

January 23, 2023 · 2 min · 343 words · Me

## Leetcode 217: Contains Duplicates

Problem Statement Description Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct. Examples Example 1: Input: nums = [1,2,3,1] Output: true Example 2: Input: nums = [1,2,3,4] Output: false Example 3: Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true Constraints 1 <= nums.length <= 105 -109 <= nums[i] <= 109 Key Insights This is a very simple problem that introduces the concept of a hash set....

January 18, 2023 · 1 min · 201 words · Me

## Leetcode 876: Middle of the Linked List

Problem Statement Description Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node. Examples Example 1: flowchart LR a((1))-->b((2))-->c(3)-->d((4))-->e((5)) Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3. Example 2: flowchart LR a((1))-->b((2))-->c((3))-->d(4)-->e((5))-->f((6)) Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one....

January 17, 2023 · 3 min · 487 words · Me

## Leetcode 543: Diameter of a Binary Tree

Problem Statement Description Given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them. Examples Example 1: flowchart TD a((1))-->b((2)) b-->c((4)) b-->d((5)) a-->e((3)) Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3]....

January 16, 2023 · 3 min · 492 words · Me

## Leetcode 169: Majority Element

Problem Statement Description Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Examples Example 1: Input: nums = [3,2,3] Output: 3 Example 2: Input: nums = [2,2,1,1,1,2,2] Output: 2 Constraints n == nums.length 1 <= n <= 5 * 104 -109 <= nums[i] <= 109 Key Insights There are many different ways to solve this problem....

January 16, 2023 · 2 min · 249 words · Me