Problems Solved

This section contains solutions to problems from NeetCode practice.

1929. Concatenation of Array

Problem Statement:

Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n (0-indexed).

Specifically, ans is the concatenation of two nums arrays.

Return the array ans.

Approach:

Create a new array of length 2n and copy the original array twice.

Time Complexity: $O(n)$ - need to copy all elements
Space Complexity: $O(n)$ - creating new array of size $2n$

Solution 1: Naive Approach

#![allow(unused)]
fn main() {
pub fn get_concatenation(nums: Vec<i32>) -> Vec<i32> {
    let l = nums.len();
    let mut result = Vec::<i32>::with_capacity(l * 2);
    for item in nums.iter() {
        result.push(*item);
    }
    for item in nums.iter() {
        result.push(*item);
    }
    result
}
}

Notes:

• Uses explicit loops, clear but verbose
• Pre-allocates capacity for efficiency

Solution 2: Using extend_from_slice

#![allow(unused)]
fn main() {
impl Solution {
    pub fn get_concatenation(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut ans = Vec::with_capacity(2 * n);

        // Append nums twice
        ans.extend_from_slice(&nums);
        ans.extend_from_slice(&nums);

        ans
    }
}
}

Notes:

• Uses extend_from_slice which is more efficient for slices
• Pre-allocates capacity
• More idiomatic than explicit loops

Solution 3: Using Iterator Chain

#![allow(unused)]
fn main() {
impl Solution {
    pub fn get_concatenation(nums: Vec<i32>) -> Vec<i32> {
        nums.iter()
            .chain(nums.iter())
            .cloned()
            .collect()
    }
}
}

Notes:

• Most idiomatic Rust style
• Uses iterator chain for functional programming approach
• Concise and readable

Examples:

#![allow(unused)]
fn main() {
// Input: nums = [1,2,1]
// Output: [1,2,1,1,2,1]

// Input: nums = [1,3,2,1]
// Output: [1,3,2,1,1,3,2,1]
}

20. Valid Parentheses

Problem Statement:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Approach:

Use a stack to keep track of opening brackets. When we encounter a closing bracket, check if it matches the most recent opening bracket (top of stack). If the stack is empty at the end, all brackets were properly matched.

Time Complexity: $O(n)$ - single pass through the string
Space Complexity: $O(n)$ - stack can contain up to $n/2$ elements in worst case

Solution:

#![allow(unused)]
fn main() {
impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut stack: Vec<char> = Vec::new();

        for ch in s.chars() {
            match ch {
                '(' | '{' | '[' => stack.push(ch),
                ')' => {
                    if stack.pop() != Some('(') {
                        return false;
                    }
                }
                '}' => {
                    if stack.pop() != Some('{') {
                        return false;
                    }
                }
                ']' => {
                    if stack.pop() != Some('[') {
                        return false;
                    }
                }
                _ => return false, // not strictly needed for this problem
            }
        }

        stack.is_empty()
    }
}
}

Notes:

• Uses a stack to track opening brackets
• When encountering a closing bracket, check if it matches the top of the stack
• Return false immediately if mismatch is found
• Final check ensures all brackets were closed (stack is empty)

Examples:

#![allow(unused)]
fn main() {
// Input: s = "()"
// Output: true

// Input: s = "()[]{}"
// Output: true

// Input: s = "(]"
// Output: false

// Input: s = "([)]"
// Output: false

// Input: s = "{[]}"
// Output: true
}