# Minimum Dot Product

This problem was taken from the *Coursera ***Data Structures and Algorithms Specialization**, specifically from the** ****Algorithmic Toolbox Course**, Week 3:**Greedy Algorithms**, that I’ve recently completed. If you are taking that course or plan to take that course, please **don’t look ahead** at the solution as it will be against the Honor Code and won’t do you any good.

#### Problem Introduction

The dot product of two sequences a(1) , a(2) , . . . , a(n) and b(1) , b(2) , . . . , b(n) of the same length is equal to a(1) b(1) + a(2) b(2) + · · · + a(n) b(n)

#### Problem Description

**Task:** The goal is, given two sequences a(1) , a(2) , . . . , a(n) and b(1) , b(2) , . . . , b(n) , find a permutation π of the second sequence such that the dot product of a(1) , a(2) , . . . , a(n) and b(π 1) , b(π 2) , . . . , b(π n) is minimum.**Input Format:** The first line contains an integer **n**, the second one contains a sequence of integers a(1) , a(2) , . . . , a(n) , the third one contains a sequence of integers b(1) , b(2) , . . . , b(n) .**Constraints:** 1 ≤ **n** ≤ 10^3 ; −10^5 ≤ **a(i)** , **b(i)** ≤ 10^5 for all 1 ≤ i ≤ n.**Output Format:** Output the **minimum possible dot product**.**Time Limits:** C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.**Memory Limit:** 512 Mb

#### Sample 1

**Input:**1

23

39

**Output:**

897

**Explanation:**

In this case, 897 is just the only possible dot product.

#### Sample 2

**Input:**3

1 3 -5

-2 4 1

**Output:**

-25

**Explanation:**

−25 = 1 · 1 + 3 · (−2) + (−5) · 4.

#### What To Do

The first thing to note is that the problem can be restated as follows: partition two input sequences a = (a(1) , a(2) , . . . , a(n)) and b = (b(1) , b(2) , . . . , b(n) ) into **n pairs** of the form (a(i) , b(j) ) such that the sum of their products is minimum.

We claim that it is safe to multiply a maximum element of **a** by a minimum element of **b**. We illustrate this by a toy example. Assume that **n = 4** and that **a(2)** = **max{a(1) , a(2) , a(3) , a(4) }** and **b(1)** = **min{b(1) , b(2) , b(3) , b(4) }**.

Consider a candidate solution:

a(1) b(3) + a(2) b(4) + a(3) b(1) + a(4) b(2)

Here, **a(2)** is multiplied by **b(4)** and **b(1)** is multiplied by **a(3)** . Let’s show that if we **“swap”** these two pairs, then the total value can only decrease. Indeed, the difference between dot products of these two solutions is equal

to (a(1) b(3) + a(2) b(4) + a(3) b(1) + a(4) b(2) ) − (a(1) b(3) + a(2) b(1) + a(3) b(4) + a(4) b(2) ) = a(2) b(4) + a(3) b(1) − a(2) b(1) − a(3) b(4) = (a(2) − a(3) )(b(4) − b(1) ) .

It is non-negative, since a(2) ≥ a(3) and b(4) ≥ b(1)

### My Solution:

**If you can think of any other way to improve this algorithm or if you could point out something that you think I did wrong, you’re more than w elcome to reach out to me by responding to this and pointing out the mistakes. If you like this solution, please hit the “Recommend” button below, it’ll mean a lot to me. Thanks.**