Product of Array Except Self

In this blog, we will discuss the "Product of Array Except Self" problem, which is a popular problem in coding interviews. We will go through the problem statement, explain the approach, and provide both brute force and optimal solutions. Additionally, we will perform a dry run of the code for better understanding and analyze the time and space complexity of each solution.

Problem Statement with Example

Given an integer array nums, the task is to return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.

Let's consider an example to understand the problem:

Example 1:

Input: nums = [1, 2, 3, 4]

Output: [24, 12, 8, 6]

Explanation: The product of all elements except the element at index 0 is 2*3*4 = 24. Similarly, for index 1, it is 1*3*4 = 12, for index 2, it is 1*2*4 = 8, and for index 3, it is 1*2*3 = 6.

Example 2:

Input: nums = [-1, 1, 0, -3, 3]

Output: [0, 0, 9, 0, 0]

Explanation: The product of all elements except the element at index 0 is 1*0*(-3)*3 = 0. Similarly, for index 1, it is -1*0*(-3)*3 = 0, for index 2, it is -1*1*(-3)*3 = 9, for index 3, it is -1*1*0*3 = 0, and for index 4, it is -1*1*0*(-3) = 0.

Practice: Leetcode Link Leetcode

Brute Force Solution

We can solve this problem using a brute force approach by iterating over the array and calculating the product of all elements except the current one for each element. However, this approach will have a time complexity of O(n^2), which is not efficient for large arrays.

Algorithm/Pseudocode


// Brute Force Approach
1. Initialize an array 'answer' of the same length as 'nums' and fill it with 1.
2. For each element in 'nums' at index i:
    a. Initialize a variable 'product' to 1.
    b. For each element in 'nums' at index j:
        i. If i is not equal to j, multiply 'product' by nums[j].
    c. Assign 'product' to answer[i].
3. Return the 'answer' array.

Java Code for Brute Force Solution

package codeKatha;

public class ProductOfArrayExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    product *= nums[j];
                }
            }
            answer[i] = product;
        }

        return answer;
    }
}

Dry Run

Let's dry run the brute force solution with an example:

Input: nums = [1, 2, 3, 4]

Step 1: Initialize answer = [1, 1, 1, 1]

Step 2: Iterating over each element in nums:
- For i = 0: product = 1
    - For j = 0: skip (i == j)
    - For j = 1: product = 1 * 2 = 2
    - For j = 2: product = 2 * 3 = 6
    - For j = 3: product = 6 * 4 = 24
    - answer[0] = 24

- For i = 1: product = 1
    - For j = 0: product = 1 * 1 = 1
    - For j = 1: skip (i == j)
    - For j = 2: product = 1 * 3 = 3
    - For j = 3: product = 3 * 4 = 12
    - answer[1] = 12

- For i = 2: product = 1
    - For j = 0: product = 1 * 1 = 1
    - For j = 1: product = 1 * 2 = 2
    - For j = 2: skip (i == j)
    - For j = 3: product = 2 * 4 = 8
    - answer[2] = 8

- For i = 3: product = 1
    - For j = 0: product = 1 * 1 = 1
    - For j = 1: product = 1 * 2 = 2
    - For j = 2: product = 2 * 3 = 6
    - For j = 3: skip (i == j)
    - answer[3] = 6

Step 3: Return answer = [24, 12, 8, 6]

Time and Space Complexity

Time Complexity: O(n2) - For each element, we are iterating through the entire array to calculate the product.

Space Complexity: O(n) - We are using an extra array to store the result.

Optimized Solution

To optimize this solution, we can use two additional arrays to store the product of all elements to the left and right of each element. This will allow us to calculate the final product for each element in O(n) time.

Algorithm/Pseudocode


// Optimized Approach
1. Initialize two arrays, 'leftProducts' and 'rightProducts', of the same length as 'nums' and fill them with 1.
2. Initialize an array 'answer' of the same length as 'nums' and fill it with 1.
3. Fill 'leftProducts' such that leftProducts[i] contains the product of all elements to the left of 'nums[i]'.
4. Fill 'rightProducts' such that rightProducts[i] contains the product of all elements to the right of 'nums[i]'.
5. For each element in 'nums' at index i:
    a. answer[i] = leftProducts[i] * rightProducts[i].
6. Return the 'answer' array.

Java Code for Optimized Solution

package codeKatha;

public class ProductOfArrayExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] leftProducts = new int[n];
        int[] rightProducts = new int[n];
        int[] answer = new int[n];

        // Fill leftProducts
        leftProducts[0] = 1;
        for (int i = 1; i < n; i++) {
            leftProducts[i] = nums[i - 1] * leftProducts[i - 1];
        }

        // Fill rightProducts
        rightProducts[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            rightProducts[i] = nums[i + 1] * rightProducts[i + 1];
        }

        // Fill answer
        for (int i = 0; i < n; i++) {
            answer[i] = leftProducts[i] * rightProducts[i];
        }

        return answer;
    }
}

Dry Run

Let's dry run the optimized solution with an example:

Input: nums = [1, 2, 3, 4]

Step 1: Initialize leftProducts = [1, 1, 1, 1]
Step 2: Initialize rightProducts = [1, 1, 1, 1]
Step 3: Initialize answer = [1, 1, 1, 1]

Step 4: Fill leftProducts:
- leftProducts[1] = 1 * 1 = 1
- leftProducts[2] = 2 * 1 = 2
- leftProducts[3] = 3 * 2 = 6

leftProducts = [1, 1, 2, 6]

Step 5: Fill rightProducts:
- rightProducts[2] = 4 * 1 = 4
- rightProducts[1] = 3 * 4 = 12
- rightProducts[0] = 2 * 12 = 24

rightProducts = [24, 12, 4, 1]

Step 6: Fill answer:
- answer[0] = 1 * 24 = 24
- answer[1] = 1 * 12 = 12
- answer[2] = 2 * 4 = 8
- answer[3] = 6 * 1 = 6

Step 7: Return answer = [24, 12, 8, 6]

Time and Space Complexity

Time Complexity: O(n)- We are iterating through the array three times, which is linear.

Space Complexity: O(n) - We are using two extra arrays to store the left and right products.

More Optimized Solution

We can further optimize the solution by using the output array itself to store the left products, and we can calculate the right products on the fly.

Algorithm/Pseudocode


// More Optimized Approach
1. Initialize an array 'answer' of the same length as 'nums' and fill it with 1.
2. Fill 'answer' such that answer[i] contains the product of all elements to the left of 'nums[i]'.
3. Initialize a variable 'rightProduct' to 1.
4. Traverse the array from right to left and update 'answer' such that it contains the product of all elements except 'nums[i]'.
5. Return the 'answer' array.

Java Code for More Optimized Solution

package codeKatha;

public class ProductOfArrayExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        // Fill answer with left products
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }

        // Calculate right products on the fly and update answer
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return answer;
    }
}

Dry Run

Let's dry run the more optimized solution with an example:

Input: nums = [1, 2, 3, 4]

Step 1: Initialize answer = [1, 1, 1, 1]

Step 2: Fill answer with left products:
- answer[1] = 1 * 1 = 1
- answer[2] = 2 * 1 = 2
- answer[3] = 3 * 2 = 6

answer = [1, 1, 2, 6]

Step 3: Initialize rightProduct = 1

Step 4: Traverse from right to left and update answer:
- i = 3: answer[3] *= 1 => answer[3] = 6
           rightProduct *= 4 => rightProduct = 4
- i = 2: answer[2] *= 4 => answer[2] = 8
           rightProduct *= 3 => rightProduct = 12
- i = 1: answer[1] *= 12 => answer[1] = 12
           rightProduct *= 2 => rightProduct = 24
- i = 0: answer[0] *= 24 => answer[0] = 24
           rightProduct *= 1 => rightProduct = 24

Step 5: Return answer = [24, 12, 8, 6]

Time and Space Complexity

Time Complexity: O(n)- We are iterating through the array three times, which is linear.

Space Complexity: O(1) - We are using the output array itself to store the left products and calculating the right products on the fly.

Edge Cases

1. If the input array contains only one element, the output should be an empty array or an array with a single element 1 because there are no other elements to multiply.

2. If the input array contains zero, the product for the indices other than the zero index will be zero unless there is more than one zero.

By understanding these solutions, even a novice can grasp the concepts and apply the optimal approach for solving the "Product of Array Except Self" problem efficiently.

Related categories:

Comments

Post a Comment

Popular Posts on Code Katha

Java Interview Questions for 10 Years Experience

Image
Welcome to the comprehensive guide on "Java Interview Questions for 10 Years Experience." Java has been one of the most popular programming languages for decades, and its widespread adoption means that the demand for skilled Java developers has never been higher. If you are someone who has been working with Java for the last decade, you have accumulated a wealth of experience and knowledge that you can showcase during interviews. Recommended  to read and brush up for your interview: Must know interview questions and concept for any Java Interview Spring boot interview Questions for 10 years experiance These simple and short articles help you to add AI to your resume and enhance the chance of selection: Java Spring Boot AI with Ollama Java Spring Boot AI with Open AI (Chat GPT) This blog post will provide you with a list of commonly asked interview questions for 10 years experienced Java developers. It will also include detailed answers to each question, with explanat...
Read more

Sql Interview Questions for 10 Years Experience

Image
As an experienced SQL professional, you might encounter challenging questions during a job interview. In this blog post, we will explore 10 common SQL interview questions and provide in-depth explanations along with relevant examples. Let's dive in! Contents [ hide ] What is SQL Injection, and how can you prevent it? SQL Injection is a malicious attack where an attacker manipulates input data to execute unintended SQL statements. It can lead to unauthorized access, data breaches, and data manipulation. To prevent SQL Injection, follow these best practices: 1.1. Use Prepared Statements: Prepared statements or parameterized queries separate SQL code from data input, preventing attackers from injecting malicious SQL code. Here's an example in PHP: $stmt = $pdo->prepare('SELECT * FROM users WHERE username = :username'); $stmt->bindParam(':username', $username); $stmt->execute(); 1.2. Sanitize User Input: Validate and sanitize user input ...
Read more

Spring Boot Interview Questions for 10 Years Experience

Image
Welcome to the comprehensive guide on "Spring Boot Interview Questions for 10 Years Experience". Spring Boot has become one of the most popular frameworks for developing enterprise-grade applications, and its widespread adoption means that the demand for skilled Spring Boot developers has never been higher. If you are someone who has been working with Spring Boot for the last decade, you have accumulated a wealth of experience and knowledge that you can showcase during interviews. Recommended  to read and brush up for your interview: Must know interview questions and concept for any Java Interview Java Interview Questions for 10 Years Experience These simple and short articles help you to add AI to your resume and enhance the chance of selection: Spring Boot AI with Ollama Spring Boot AI with Open AI (Chat GPT) This blog post will provide you with a list of commonly asked interview questions for 10 years expe...
Read more

Java interview questions - Must to know concepts

Contents [ hide ] How does Java achieve platform independence, and what is the underlying principle? Java programs can run on diverse operating systems and hardware setups without requiring modification. This feat is primarily achieved through the concept of the Java Virtual Machine (JVM). The Java Virtual Machine (JVM) The JVM acts as a bridge between the Java code you write and the underlying hardware and operating system . When you compile your Java code, it is translated into an intermediate form called bytecode, which is not tied to any specific platform. The JVM then comes into play. It takes this bytecode and dynamically translates it into machine-specific instructions that the host system can execute. This means that a Java program can be written once and executed on any system with the appropriate JVM for that system. Example: Running a Java Program on Different Platforms Consider a simple Java program that calculates the sum of two numbers: package codeKatha...
Read more

Visual Studio Code setup for Java and Spring with GitHub Copilot

Image
Introduction- In this tutorial blog, we will explore the process of setting up and utilising Visual Studio Code for Java programming, as well as incorporating GitHub Copilot as a valuable coding tool. Visual Studio Code is a powerful and versatile code editor that offers a wide range of features and extensions for Java developers. By using Visual Studio Code for Java programming, developers can benefit from features such as code completion, debugging, and live coding. Additionally, with the integration of GitHub Copilot, developers can streamline their coding process with AI-assisted suggestions for code snippets and functions. This blog will provide a comprehensive guide for setting up and using these tools for Java development. Contents [ hide ] Setup Visual Studio Code for Java and Spring Visual Studio Code (VS Code) is an open-source code editor that supports a wide range of programming languages, including Java. It is a powerful tool...
Read more

Data Structures & Algorithms Tutorial with Coding Interview Questions

Image
About the Course This course offers comprehensive coverage of coding questions that serve as a solid foundation for understanding DSA concepts. These questions are frequently asked in coding interviews, either directly or with some variations, by many companies, including Adobe, Facebook (Meta), Paytm, Amazon, Google, and others. Our primary objective is to enhance your problem-solving skills and enable you to devise optimal solutions. The course includes a wide range of topics, such as Arrays, Strings, Searching and Sorting, Greedy Algorithms, Trees, Graphs, Dynamic Programming, and more. Upon completion, you will possess the necessary skills to ace DSA interviews for typical companies or excel in the initial rounds of product-based companies such as Google, Microsoft and similar others. We are started with Graph data Structure and add others soon. Contents [ hide ] Approach Our course is  organised into chapters ...
Read more

Spring AI with Ollama

Image
Introduction to Spring AI with Ollama Welcome to a comprehensive guide on leveraging Spring AI with Ollama to develop AI-driven applications using Java. This tutorial will cover everything from setting up Ollama locally, configuring your development environment, to creating an application that utilizes large language models for text generation. Contents [ hide ] Setting Up Ollama Installing Ollama To use Ollama locally, you must first install it on your machine. This involves downloading the Ollama software from the official repository and configuring it to run without Docker. Follow the installation instructions provided in the Ollama README file available on their official GitHub page . Ollama Download link Downloading the Mistral Model After setting up Ollama, you can download the Mistral model directly from the Ollama management interface. Mistral is designed for a broad range of applications, offering robust text generation capabilities. // Run this command in cl...
Read more

Spring Data JPA

Image
Introduction- We will learn here Spring Data JPA, perform CRUD operation, Clear concept of Relationship mapping like one-to-many, many-to-one with Example. Spring Data JPA is a powerful framework that simplifies the process of working with relational databases in Java applications. It provides an easy-to-use API for working with JPA, allowing developers to focus on their business logic instead of worrying about the details of how JPA works. With Spring Data JPA, you can easily define entities that map to database tables, and then use them to perform CRUD (create, read, update, delete) operations on those tables. In addition, Spring Data JPA provides support for more advanced features like querying and pagination, making it an excellent choice for both small and large projects. Contents [ hide ] In this blog, we will explore Spring Data JPA by building a sample application that uses it to manage users and packs. But, before let...
Read more

Topological Sort in Graph

Welcome to our beginner's guide to Topological Sort in Graph Theory! Topological Sort is an essential algorithm used to order the vertices of a directed graph such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. Let's explore this important concept together! Contents [ hide ] Understanding the Problem Statement Before delving into Topological Sort, let's understand the problem it addresses. Consider a scenario where tasks depend on one another; for example, in a project where certain tasks must be completed before others can begin. Such dependencies can be modeled using directed graphs, where nodes represent tasks and directed edges represent dependencies between tasks. The goal of Topological Sort is to find a linear ordering of the vertices of the graph such that for every directed edge uv, the vertex u comes before the vertex v in the ordering. This ordering provides a sequence in which the tasks can be perf...
Read more

Bit Manipulation and Bit Masking Concepts

Image
Introduction- A bit is the fundamental unit of information used in computing and digital communication.We generally worked on decimal numbers having values from 0,1,2.. to 9. Similarly binary system is characterized by two possible values, usually expressed as 0 or 1. In terms of electronic switch we can say 0 denotes an OFF switch and 1 denotes an ON switch. In terms of magnetic domain on a hard drive, we can say 0 denotes an unmagnetized domain, and 1 denotes a magnetized domain. Contents [ hide ] Uses of bit manipulation concepts in our coding Bit manipulation is a technique that can give programmers a significant performance advantage in certain algorithms. It can help to reduce the time complexity. By working directly with binary data using bitwise operators, we can perform operations faster than with traditional arithmetic operations. The reason for this is simple: computers understand binary data. When we perform any operation, it g...
Read more