Max and Min Products

Slug: max-and-min-products3347 Difficulty: Medium Id: 702739 Topic Tags: Arrays, Data Structures Company Tags: None

Summary

Given an array of integers, find the maximum and minimum products that can be formed by multiplying two numbers from the given array. The array may contain duplicate elements.

The problem involves working with arrays and finding the maximum and minimum products within a set of constraints. This is a classic problem in algorithmic programming, requiring efficient algorithms to solve.

Detailed Explanation

To solve this problem, we will iterate through the array and calculate the product for each pair of numbers. We can keep track of the maximum and minimum products separately. The key idea is to find the product with the largest value (maximum product) and the product with the smallest value (minimum product).

Here's a step-by-step breakdown of the solution:

1. Initialize two variables max_product and min_product to store the maximum and minimum products, respectively.
2. Iterate through the array using a for loop.
3. For each pair of numbers in the array, calculate their product.
4. If the product is greater than max_product, update max_product.
5. If the product is less than min_product, update min_product.
6. Return the maximum and minimum products.

Here's an ASCII art diagram illustrating the algorithm:

  +---------------+
  |   Array     |
  +---------------+
          |
          v
  +---------------+
  |  Calculate    |
  |  Products     |
  +---------------+
          |
          v
  +---------------+
  |  Update max  |
  |  and min      |
  +---------------+

The time complexity of this algorithm is O(n), where n is the size of the input array. This is because we are iterating through the array once.

The space complexity is O(1), as we are only using a constant amount of space to store the maximum and minimum products.

Optimized Solutions

Java

java
public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 3, -4, 5};
        int maxProduct = findMaxAndMinProducts(arr);
        System.out.println("Maximum product: " + maxProduct);
    }

    public static int findMaxAndMinProducts(int[] arr) {
        int max_product = Integer.MIN_VALUE;
        int min_product = Integer.MAX_VALUE;

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int product = arr[i] * arr[j];
                if (product > max_product) {
                    max_product = product;
                }
                if (product < min_product) {
                    min_product = product;
                }
            }
        }

        return max_product + " " + min_product;
    }
}

Python

python
def find_max_and_min_products(arr):
    max_product = float('-inf')
    min_product = float('inf')

    for i in range(len(arr) - 1):
        for j in range(i + 1, len(arr)):
            product = arr[i] * arr[j]
            if product > max_product:
                max_product = product
            if product < min_product:
                min_product = product

    return str(max_product) + " " + str(min_product)

arr = [2, 3, -4, 5]
print("Maximum product:", find_max_and_min_products(arr))

C++

cpp
#include <iostream>
#include <vector>

int findMaxAndMinProducts(std::vector<int> arr) {
    int max_product = INT_MIN;
    int min_product = INT_MAX;

    for (int i = 0; i < arr.size() - 1; i++) {
        for (int j = i + 1; j < arr.size(); j++) {
            int product = arr[i] * arr[j];
            if (product > max_product) {
                max_product = product;
            }
            if (product < min_product) {
                min_product = product;
            }
        }
    }

    return max_product + " " + std::to_string(min_product);
}

int main() {
    std::vector<int> arr = {2, 3, -4, 5};
    int result = findMaxAndMinProducts(arr);
    std::cout << "Maximum product: " << result << std::endl;
    return 0;
}

JavaScript

javascript
function findMaxAndMinProducts(arr) {
    let max_product = Number.MIN_VALUE;
    let min_product = Number.MAX_VALUE;

    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            let product = arr[i] * arr[j];
            if (product > max_product) {
                max_product = product;
            }
            if (product < min_product) {
                min_product = product;
            }
        }
    }

    return String(max_product) + " " + String(min_product);
}

let arr = [2, 3, -4, 5];
console.log("Maximum product: ", findMaxAndMinProducts(arr));