## Heap and Heap-Sort algorithm (Java code and Leetcode problems)

Note: Heap in algorithm and data structure is a different concept with the heap in memory management. Heap in memory management is more like a pool. There is a discussion at StackOverflow, we don’t talk about the detail of this different. You know we are talking about the heap concept in algorithm and data structure is enough for us. We still follow the style of Introduction to Algorithms.

## Leetcode problem 240 Search a 2D Matrix II (Java)

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

```[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]```

Given target = `5`, return `true`.
Given target = `20`, return `false`.

## LeetCode 169 Majority Element (Java)

Given an array of size n, find the majority element. The majority element is the element that appears more than `⌊ n/2 ⌋` times.

You may assume that the array is non-empty and the majority element always exists in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

## Leecode problem 53 Maximum Subarray [Divide and conquer]（Java）

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

## LeetCode problem 23 Merge k Sorted Lists [Divide and conquer][Min-Heap]（Java）

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]
Output:
1->1->2->3->4->4->5->6

## Divide and conquer algorithm (Java code and Leetcode problems)

I am trying to solve every problem of Leetcode and write blogs to record it. Now I plan to read Introduction to Algorithms and solve problems match the book contents.

## What is Divide and conquer?

Divide and conquer is a method to solve a complex problem. When we think of a problem too complex or too big, we can try to divide the problem to some easy problems or small problems. Then we try to solve these small/easy problems and combine the results to solve the complex/big problem.

## LeetCode problem 21 Merge Two Sorted Lists（Java）

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

## LeetCode problem 992 Subarrays with K Different Integers (Java)

Given an array `A` of positive integers, call a (contiguous, not necessarily distinct) subarray of `A` good if the number of different integers in that subarray is exactly `K`.

(For example, `[1,2,3,1,2]` has `3` different integers: `1``2`, and `3`.)

Return the number of good subarrays of `A`.

Example 1:

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Example 2:

Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Note:

1. `1 <= A.length <= 20000`
2. `1 <= A[i] <= A.length`
3. `1 <= K <= A.length`

## LeetCode problem 567 Permutation in String (Java)

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

Input:
s1 = “ab”
s2 = “eidbaooo”
Output: True
Explanation: s2 contains one permutation of s1 (“ba”).

Example 2:

Input:
s1= “ab”
s2 = “eidboaoo”
Output: False

Note:

1. The input strings only contain lower case letters.
2. The length of both given strings is in the range [1, 10,000].

## LeetCode problem 438 Find All Anagrams in a String (Java)

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: “cbaebabacd”
p: “abc”
Output: [0, 6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.

Example 2:

Input:
s: “abab”
p: “ab”
Output: [0, 1, 2]
Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.