O(n) because we only iterate through nums once
use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut entries = HashMap::new();
for (i, num) in nums.iter().enumerate() {
let index = i as i32;
let difference = target - num;
let entry = entries.get(&difference);
match entry {
// the .get method of a HashMap always returns an Option containing a
// reference to the value in the map (Option<&V>),
// where V is the type of the values stored in the map.
Some(other_index) => {
return vec![*other_index, index];
},
_ => {
entries.insert(num, index);
}
}
}
vec![]
}
}O(n) because we only iterate through nums once
use std::collections::HashMap;
impl Solution {
pub fn contains_duplicate(nums: Vec<i32>) -> bool {
let mut exists = HashMap::new();
for num in nums {
if let Some(x) = exists.get(&num) {
return true;
}
exists.insert(num, true);
}
false
}
}single pass, O(n)
impl Solution {
pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
let mut results = vec![1; nums.len()];
let mut left_product = 1;
let mut right_product = 1;
let mut i = 0;
let mut j = nums.len() - 1;
while i < nums.len() {
results[i] *= left_product;
results[j] *= right_product;
left_product *= nums[i];
right_product *= nums[j];
i += 1;
j -= 1;
}
results
}
}O(n), but this works for unsorted arrays too. because of that, it's more inefficient than a solution that saves the last encountered number, and then compares the current number to the last.
use std::collections::HashMap;
impl Solution {
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
let mut exists = HashMap::new();
let mut unique = 0;
let mut i = 0;
let mut len = nums.len();
while i < len {
if let Some(x) = exists.get(&nums[i]) {
// already exists; lets remove it from the array
nums.remove(i); // mutate nums in place
len -= 1;
continue;
}
// this doesnt exist yet, so lets save it
exists.insert(nums[i], true);
i += 1;
unique += 1;
}
unique
}
}here's a simpler version that assumes a sorted list. just keeps track of the last seen number:
impl Solution {
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
let mut len = nums.len();
if len == 0 { return 0; }
let mut unique = 1;
let mut last = nums[0];
let mut i = 1;
while i < len {
if nums[i] == last {
nums.remove(i);
len -= 1;
continue;
}
last = nums[i];
i += 1;
unique += 1;
}
unique
}
}and here's one that takes advantage of built in Vector methods:
impl Solution {
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
nums.dedupe(); // mutates vector removing dupes
nums.len() as i32;
}
}this is the really weird sieve of ethoneses one. here is an explanation, but you can also look at the wikipediate article. I believe this is O(log n) because we never iterate through the array completely in the inner loop, we always start at the square of the current prime number.
There are several ways to go about solving this problem, but the classic solution is known as the sieve of Eratosthenes. For the sieve of Eratosthenes, we start by creating a boolean array (seen) of size n to represent each of the numbers less than n.
We start at 2 and for each number processed (num), we iterate through and mark each multiple (mult) of num, starting at num^2, as seen. We start at num^2 because every multiple up to the num'th multiple will have been guaranteed to have been seen before, since they're also a multiple of a smaller number. For example, when processing 5s, we can skip to 25 because 10 will have been seen when we processed 2s, 15 when we processed 3s, and 20 when we processed 2s.
Then we move num forward, skipping any numbers that have already been seen. By doing this, we will only stop on prime numbers, because they haven't been seen as a multiple of a previous iteration. We just have to update our count (ans) each time we stop and then return ans once we reach n.
impl Solution {
pub fn count_primes(n: i32) -> i32 {
let size = n as usize; // convert n to usize and use that instead; prevent i32 overflow during runtime
let mut seen = vec![false; size];
let mut count = 0;
for num in 2..size {
if seen[num] { continue; }
// we haven't seen this one; so it's a prime number
count += 1;
let mut mult = num * num; // this will overflow and cause runtime crash if using i32
while mult < size {
seen[mult as usize] = true;
mult += num;
}
}
count
}
}Here is a slightly more efficient solution, where the outer loop is bounded by the square root of n. We can make this optimization because if we're restricted to multiples <= sqrt(n), we'll still see every number up to n. I like this solution better
impl Solution {
pub fn count_primes(n: i32) -> i32 {
let size = n as usize;
if size <= 2 { return 0; }
let outer_bound = (n as f64).sqrt() as usize;
let mut seen = vec![false; size];
for i in 2..=outer_bound {
if seen[i] == false {
let mut mult = i * i;
while mult < size {
seen[mult] = true;
mult = mult + i;
}
}
}
let mut count = 0;
for i in 2..size {
if seen[i] == false { count += 1; }
}
count
}
}The slowest and most classic way is recursion. it is O(2^n). Space Complexity is O(N) because the stack increases with each recursive call.
impl Solution {
pub fn fib(n: i32) -> i32 {
if n <= 1 { return n; }
Self::fib(n - 1) + Self::fib(n - 2)
}
}Below is a more reasonable solution that doesn't require any deep math knowledge. It has O(n) time complexity and constant space complexity. Since we only need to keep track of the last two numbers in the fibonacci sequence, we just reassign variables in a linear loop.
impl Solution {
pub fn fib(n: i32) -> i32 {
if n <= 1 { return n; }
// 0 and 1 are the first two numbers of the fib sequence
let mut a = 0;
let mut b = 1;
let mut sum = 0;
for i in 2..=n {
sum = a + b; // sum becomes the next number in the sequence
a = b; // move a up one
b = sum; // move b up one
}
sum
}
}impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
let mut max_profit = 0;
let mut min = i32::MAX;
for price in prices {
if price < min {
min = price
} else if price - min > max_profit {
max_profit = price - min;
}
}
max_profit
}
}time: O(n) space: O(1)
use std::cmp;
impl Solution {
pub fn max_sub_array(nums: Vec<i32>) -> i32 {
let mut current_subarray_sum = nums[0];
let mut max_subarray_sum = nums[0];
for num in &nums[1..] {
let num = *num;
// as we iterate through the array,
// we increment by the next number in the "current" subarray
// if we find that the sum of the current subarray is less
// than the current number, we "reset" to the current number
current_subarray_sum = cmp::max(
num,
current_subarray_sum + num
);
// meanwhile, always be keeping track of the max subarray sum
// we've found
max_subarray_sum = cmp::max(
max_subarray_sum,
current_subarray_sum
);
}
max_subarray_sum
}
}