Max Area of Island

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. 

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

N Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Minimum Moves to Equal Array Elements II

 

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment or decrement an element of the array by 1.

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

Example 2:

Input: nums = [1,10,2,9]
Output: 16

 

Constraints:

• n == nums.length
• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

Approach:

This problem is deceptive in its simplicity. Ultimately, the value to which you want to set each element equal is the median of the sorted nums array. To come to this realization, we have to first think about the nature of the problem.

Let's consider a possible scenario in which we've decided that our target value is x which would take ans number of moves to complete. What would happen to ans if we increased x by 1? If we did, each element that is below the new x would have to spend another move to get up to x, but every element that is above the new x would have to spend one less move to get down to x.

This means that x should naturally move up if there are more elements above x than below. It also means the inverse, that x should move down if there are more elements below x than above. The natural outcome of this is that x will settle at a spot where there are the same number of elements on either side, which is the median value of nums.

To find the median value, we'll have to first sort nums. If nums has an even number of elements, any value between the two middle elements, inclusive, will work for calculating the answer, so we don't have to worry about which of the two elements we use for our solution.

After we have the median value, we can just iterate through nums and find the sum of the differences of each number from the median value, which should be our answer.

Mathematical Proof

C++ Code:

int minMoves2(vector<int>& nums) {
	sort(begin(nums), end(nums));
	int moves = 0, median = nums[size(nums) / 2];
	for(auto num : nums) moves += abs(num - median);
	return moves;
}

Java Code:

class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int ans = 0, median = nums[(nums.length / 2)];
        for (int num : nums) ans += Math.abs(median - num);
        return ans;
    }
}

Python Code:

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        ans, median = 0, nums[len(nums) // 2]
        for num in nums: ans += abs(median - num)
        return ans

• Time Complexity: O(N * log N) where N is the length of nums, for sorting nums
• Space Complexity: O(1)

💻🐱‍💻If there are any suggestions / questions / mistakes in my post, please do comment below 👇