# 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.

Divide and conquer is easy when you can easily find out how to divide a problem. But a lot of times how to divide a problem is hard. And different problem always needs a different divide approach. So if you want to master all divide and conquer problems you need to do a lot of practices. Only this way you can build a strong understanding of the thought of divide and conquer, and get more feeling of familiarity, and master more method to divide.

Chapter 2.3.1 of Introduction to Algorithms introduces Merge sort algorithm, Chapter 4 “Divide and conquer” introduces The maximum-subarray problem and Strassen’s algorithm for matrix multiplication.

I implement these three algorithms from pseudocode from the book to Java code:

### Strassen’s algorithm for matrix multiplication Java version:

#### Simple recursive

Helper functions

Matrix split and combine functions

Matrix add and minus functions

Strassen’s algorithm for matrix multiplication

## LeetCode divide and conquer problems list

 4 Median of Two Sorted Arrays Hard 23 Merge k Sorted Lists Hard 53 Maximum Subarray Easy 169 Majority Element Easy 215 Kth Largest Element in an Array Medium 218 The Skyline Problem Hard 240 Search a 2D Matrix II Medium 241 Different Ways to Add Parentheses Medium 282 Expression Add Operators Hard 312 Burst Balloons Hard 315 Count of Smaller Numbers After Self Hard 327 Count of Range Sum Hard 493 Reverse Pairs Hard 514 Freedom Trail Hard 426 Convert Binary Search Tree to Sorted Doubly Linked List Medium 903 Valid Permutations for DI Sequence Hard 932 Beautiful Array Medium 973 K Closest Points to Origin  This site uses Akismet to reduce spam. Learn how your comment data is processed.