No Specialist Knowledge Required

Steven Curtis

Nov 30, 2020·3 min read

This article is about the 4 challenges in the LeetCode Weekly Contest 217. That is it!

1672 Richest Customer Wealth
1673 Find the Most Competitive Subsequence
1674 Minimum Moves to Mkae Array Complementary
1675 Minimize Deviation in Array

The solutions may assume some knowledge of Big O notation

The Problems

Each problem will be approached in turn, with a solution and also with articles explaining the tools, techniques and theory that will help you solve these problems yourself.

Let us get started!

1672 Richest Customer Wealth

Accounts are given as a two-dimensional grid accounts[i][j] where the row represents the customer:

The question asks us to sum the accounts for each customer, and return the largest sum of each customer.

For this solution I’ve closen to use reduce to create the sum of a customer’s accounts. The solution is given in the following class:

1673 Find the Most Competitive Subsequence

This challenge tasks us with finding the most competitive subsequence in an arrray. We are using an array essentially as a stack, but save space (and time!) since we are going to use this stack as the result array.

We find that the competitive subsequence is the smallest number.

We are given an array, and a length which represents how long the candidate subsequences are. A subsequence is a sequence generated from the array deleting some elements of the array without changing the order of the array.

So how can we find the smallest possible number result?

1674 Minimum Moves to Make an Array Complementary

An array is said to be complementary if for indicies i in an array nums has a limit and a length of n, then the following has the same result for all i, that is: nums[i] + nums[n - 1 - i].

In order to make the array complementary to a Target we can make a moves:

• Replace an Integer from nums with a number from 1 to limit

So what is the minimum number of those moves that we would need to make a given nums array complementary (as defined above).

A complementary array nums consists of pairs A = nums[i], B = nums[n - 1 - i] where A + B = Target. There are 5 possible solutions for (A, B) given a Target:

1. 2 <= Target < min(A, B) + 1 both A and B need to be made smaller - so 2 operations are required
2. min(A, B) + 1 <= T < A + B Make the larger of A and B smaller - one operation required
3. T = A + B - No operations are needed
4. A + B < T < max(A, B) + limit - Make the smaller of A and B larger - one operation required
5. max(A, B) + limit < T <= 1 * limit - both A and B need to be larger - so 2 operations are required

we use a memo to store the moves, much in the way that we would for subarray sum.

1675 Minimize Deviation in Array

Given an array nums containing n positive integers return the minimum difference between all the elements in the array.

To limit the differencce there are two operations that can be performed on the Array:

• Divide an even element by 2
• Multiply an odd element by 2

Theory

The largest off factor of all the numbers can be calculated by traversing the nums array, and this is maxOdd factor that we pick operations that will transform the list as close as possible to maxOdd.

We then traverse the nums array, and we calculate a list of pairs defined as var dev: [(Int, Int)] = []

We then sort the pairs, and work out the minimal sum:

Putting it all together:

Conclusion

I hope this article has helped you out!

If you’ve any questions, comments or suggestions please hit me up on Twitter