2
\$\begingroup\$

It's taking 2.4 MB of memory and 20 ms. It's my solution for Two Sum problem on LeetCode. How can I make it better using closures and other stuff? Kindly review the code.

use std::convert::TryInto;
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) ->Vec<i32> {
        let mut status:bool = false;
        let mut result:Vec<i32> = Vec::with_capacity(2);
        let rang = nums.len()-1;
        if (nums.len() < 2 || nums.len() > 10_0000) && (target < -1000000000 || target > 1000000000){
            panic!("Too few or too much values");
        }else{
            
            'outer: for (i, val) in nums.iter().enumerate() {
                if nums[i] < -1000000000 || nums[i] > 1000000000{
                    panic!("Too large or too small value in vec");
                }
                'inner: for j in i+1..nums.len() {
                            // println!("{}", nums[i]);
                             if nums[i] + nums[j] == target {
                                // println!("Hanji paaji mil gye ney..");
                                status = true;
                                // result[0] = x.try_into().unwrap();
                                // result[1] = (x+1).try_into().unwrap();
                                result.push(i.try_into().unwrap());
                                result.push((j).try_into().unwrap());
                                // result
                                break 'outer;
                            }else{
                                continue;
                            }
                        }
                }
        }   
        if status{
            result
           }else{
               panic!("Not found");
           }
        //  result
    }
}
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Proper name and description

Rename the question and give it proper description and tags according to https://codereview.stackexchange.com/help/how-to-ask

Indent the code

Unindented code looks ugly. Moreover, it has bad readability. Compare this

    if status {
        result
    } else {
        panic!("Not found");
    }

with your code. See the difference? (Returning) result and panicking happen on the same level. Else is the counterpart of if, not its internal structure. I don't need to look for curly brackets to say that - indentation does it. You'll save your own time indenting the code.

Cleanup

You've done some debugging output. It's ok (btw check out the dbg! macro). But once the code is tested you don't need it anymore. It's ok to have commented out lines while debugging, but when it's done - remove them. Clean code is much better to read. The same goes for unused variables. Rust even gives you a warning for that - don't ignore the warnings!

Validation and algorithm separation

While not always possible, it is a hood habit to validate data before the algorithm begins. I don't think you need validation here (it is stated that input data will be ok), but if you still want to validate - do it on the beginning. To have the same loop for validation and for searching reduces the readability. Also recheck the validation conditions - it looks like something is wrong there.

Labels

Go To statement considered harmful. Yes, this is break statement, which is much better, but once again - could you do any better? Yes, of course - when the answer is found, you can simply return it! No need to have labels ('inner is not needed even now) and status variable! That's simple! Also in this case you should not create a result variable - just construct it on return.

Else after return/panic

Sometimes it's good, especially if you want to show that something else could happen instead of returning (like logging the error). Sometimes not. Right here it's increasing nesting and can be omitted.

Continue at the end of the loop

Unnecessary, the loop will continue anyway.

Unnecessary complication and includes

Try_into? YAGNI. You've just validated the data, indexes can't be out of 0..100_000 (btw check out this constraint - it looks like something wrong with it), so simple as is enough:

result.push(i as i32)

So, the code now goes as

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) ->Vec<i32> {
        if (nums.len() < 2 || nums.len() > 10_0000) || (target < -1000_000_000 || target > 1000_000_000){
            panic!("Wrong input data");
        }
        for &val in nums.iter() {
            if val < -100_0000_000 || val > 1000_000_000{
                panic!("Too large or too small value in vec");
            }
        }
            
        for (i, val_i) in nums.iter().enumerate() {
            for j in i+1..nums.len() {
                if val_i + nums[j] == target {
                    return vec![i as i32, j as i32];
                }
            }
        }   
        panic!("Not found");
    }
}

Choosing better algorithm

You have \$O(n^2)\$ complexity: n for choosing an element to check and n for looking up for its counterpart. You can do something with ...Set or ...Map, but the most obvious way is to build a sorted Vec (\$O(n \ln(n))\$), then move from the both sides (i increasing from 0 if v[i] + v[j] is lower than the target, j decreasing from nums.len() - 1 if v[i] + v[j] is higher) until a sum is found, and then search for indexes in the nums (\$O(n)\$).

\$\endgroup\$
7
  • 2
    \$\begingroup\$ Re i as i32: the Rust cheatsheet, together with many Rust programmers, recommends .try_into() over as, since the former makes the fallible nature of type conversion explicit, whereas the latter silently produces bogus results in case of error. I wouldn't blame OP for using .try_into(). Of course, LeetCode was the one who introduced this conversion by using the wrong type in the first place :/ \$\endgroup\$
    – L. F.
    Commented Jun 29, 2021 at 8:42
  • 1
    \$\begingroup\$ That's right - but here we validate data (vec size) before converting, so as will do. Without validation, of course, try_into() is better. \$\endgroup\$ Commented Jun 29, 2021 at 9:26
  • \$\begingroup\$ now reduced to 16ms and 2.1MB . \$\endgroup\$ Commented Jun 29, 2021 at 12:33
  • \$\begingroup\$ Have you done the last paragraph? \$\endgroup\$ Commented Jun 29, 2021 at 13:22
  • \$\begingroup\$ ``` use std::collections::HashMap; impl Solution { pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> { let mut num_to_idx: HashMap<i32, i32> = HashMap::new(); for (idx, num) in nums.iter().enumerate(){ match num_to_idx.get(&(target - *num)){ Some(&idx2) => return vec![idx as i32, idx2], None => num_to_idx.insert(*num, idx as i32), }; } vec![] } } ``` Top solution from leetcode(speed wise), where constraints are being checked here? like value < 1000000000 \$\endgroup\$ Commented Jun 29, 2021 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.