Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
// Product of Array Except Self - https://leetcode.com/problems/product-of-array-except-self/description/ class Solution { // Brute Force // Time Complexity: O(n^2) // Space Complexity: O(1) // Below solution leads to Time Limit Exceeded on LeetCode // public int[] productExceptSelf(int[] nums) { // int[] answer = new int[nums.length]; // for(int i = 0; i < nums.length; i++) { // int product = 1; // for (int j = 0; j < nums.length; j++) { // if (i != j) { // product *= nums[j]; // } // } // answer[i] = product; // } // return answer; // } // Ignoring the Division constraint // Time Complexity: O(n) // Space Complexity: O(1) // Below solution doesn't work when input array has 0 // public int[] productExceptSelf(int[] nums) { // int[] answer = new int[nums.length]; // int arrayProduct = 1; // for(int i = 0; i < nums.length; i++) { // arrayProduct *= nums[i]; // } // for(int i = 0; i < nums.length; i++) { // if (nums[i] != 0) { // answer[i] = arrayProduct / nums[i]; // } // } // return answer; // } // Using Prefix & Suffix products // Time Complexity: O(n) // Space Complexity: O(n) public int[] productExceptSelf(int[] nums) { int[] answer = new int[nums.length]; int[] prefix = new int[nums.length]; int[] suffix = new int[nums.length]; // prefixes prefix[0] = 1; for(int i = 1; i < nums.length; i++) { prefix[i] = prefix[i - 1] * nums[i - 1]; } // suffixes suffix[nums.length - 1] = 1; for(int i = nums.length - 2; i >= 0; i--) { suffix[i] = suffix[i + 1] * nums[i + 1]; } for(int i = 0; i < nums.length; i++) { answer[i] = prefix[i] * suffix[i]; } return answer; } }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)