Top 10 Medium-Level DSA Questions with C++ & Java Solutions

Unknown -
0
      Top 10 Medium-Level DSA Questions with C++ & Java Solutions        
   

Top 10 Medium-Level DSA Questions (With LeetCode + C++ & Java Solutions)

   

By Nexus Coder | Last Updated: July 2025

 
 
   

📌 Why These Questions Matter

   

Medium-level DSA questions test your understanding of key concepts like hash maps, sliding windows, and recursion. They're the core of most coding interviews. This list includes the top 10 questions on LeetCode with C++ and Java solutions to help you crack your next tech interview.

 
 
   

🔥 Top 10 Medium DSA Questions with Solutions

   
         
  1.        

    1. Two Sum II - Input Array is Sorted

           

    🔗 LeetCode Link

            
    // C++
vector twoSum(vector& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return {left + 1, right + 1};
        else if (sum < target) left++;
        else right--;
    }
    return {};
}

// Java
public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) return new int[]{left + 1, right + 1};
        else if (sum < target) left++;
        else right--;
    }
    return new int[0];
}
         
    2.      
  2.        

    2. Longest Substring Without Repeating Characters

           

    🔗 LeetCode Link

            
    // C++
int lengthOfLongestSubstring(string s) {
    unordered_set set;
    int left = 0, maxLen = 0;
    for (int right = 0; right < s.length(); ++right) {
        while (set.count(s[right])) set.erase(s[left++]);
        set.insert(s[right]);
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

// Java
public int lengthOfLongestSubstring(String s) {
    Set set = new HashSet<>();
    int left = 0, maxLen = 0;
    for (int right = 0; right < s.length(); ++right) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left++));
        }
        set.add(s.charAt(right));
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}
         
    3.      
  3.        

    3. 3Sum

           

    🔗 LeetCode Link

            
    // C++
vector> threeSum(vector& nums) {
    sort(nums.begin(), nums.end());
    vector> res;
    for (int i = 0; i < nums.size(); ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.push_back({nums[i], nums[left], nums[right]});
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++; right--;
            } else if (sum < 0) left++;
            else right--;
        }
    }
    return res;
}

// Java
public List> threeSum(int[] nums) {
    Arrays.sort(nums);
    List> res = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++; right--;
            } else if (sum < 0) left++;
            else right--;
        }
    }
    return res;
}
         
    4.      
  4.        

    4. Container With Most Water

           

    🔗 LeetCode Link

            
    // C++
int maxArea(vector& height) {
    int max_area = 0;
    int left = 0;
    int right = height.size() - 1;
    while (left < right) {
        int current_area = min(height[left], height[right]) * (right - left);
        max_area = max(max_area, current_area);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max_area;
}

// Java
public int maxArea(int[] height) {
    int maxArea = 0;
    int left = 0;
    int right = height.length - 1;
    while (left < right) {
        int currentArea = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, currentArea);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}
         
    5.      
  5.        

    5. Add Two Numbers

           

    🔗 LeetCode Link

            
    // C++
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* dummyHead = new ListNode(0);
    ListNode* current = dummyHead;
    int carry = 0;
    while (l1 != nullptr || l2 != nullptr || carry != 0) {
        int val1 = (l1 != nullptr) ? l1->val : 0;
        int val2 = (l2 != nullptr) ? l2->val : 0;

        int sum = val1 + val2 + carry;
        carry = sum / 10;
        current->next = new ListNode(sum % 10);
        current = current->next;

        if (l1 != nullptr) l1 = l1->next;
        if (l2 != nullptr) l2 = l2->next;
    }
    return dummyHead->next;
}

// Java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode current = dummyHead;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int val1 = (l1 != null) ? l1.val : 0;
        int val2 = (l2 != null) ? l2.val : 0;

        int sum = val1 + val2 + carry;
        carry = sum / 10;
        current.next = new ListNode(sum % 10);
        current = current.next;

        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    return dummyHead.next;
}
         
    6.      
  6.        

    6. Longest Palindromic Substring

           

    🔗 LeetCode Link

            
    // C++
string longestPalindrome(string s) {
    if (s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);  // Odd length palindrome
        int len2 = expandAroundCenter(s, i, i + 1); // Even length palindrome
        int len = max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substr(start, end - start + 1);
}

int expandAroundCenter(const string& s, int left, int right) {
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

// Java
public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}
         
    7.      
  7.        

    7. Permutations

           

    🔗 LeetCode Link

            
    // C++
vector> permute(vector& nums) {
    vector> result;
    backtrack(nums, 0, result);
    return result;
}

void backtrack(vector& nums, int start, vector>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        backtrack(nums, start + 1, result);
        swap(nums[start], nums[i]); // backtrack
    }
}

// Java
public List> permute(int[] nums) {
    List> result = new ArrayList<>();
    backtrack(nums, 0, result);
    return result;
}

private void backtrack(int[] nums, int start, List> result) {
    if (start == nums.length) {
        result.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
        return;
    }
    for (int i = start; i < nums.length; i++) {
        swap(nums, start, i);
        backtrack(nums, start + 1, result);
        swap(nums, start, i); // backtrack
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
         
    8.      
  8.        

    8. Validate Binary Search Tree

           

    🔗 LeetCode Link

            
    // C++
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
bool isValidBST(TreeNode* root) {
    return isValid(root, LLONG_MIN, LLONG_MAX);
}

bool isValid(TreeNode* node, long minVal, long maxVal) {
    if (node == nullptr) {
        return true;
    }
    if (node->val <= minVal || node->val >= maxVal) {
        return false;
    }
    return isValid(node->left, minVal, node->val) && isValid(node->right, node->val, maxVal);
}

// Java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public boolean isValidBST(TreeNode root) {
    return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean isValid(TreeNode node, long minVal, long maxVal) {
    if (node == null) {
        return true;
    }
    if (node.val <= minVal || node.val >= maxVal) {
        return false;
    }
    return isValid(node.left, minVal, node.val) && isValid(node.right, node.val, maxVal);
}
         
    9.      
  9.        

    9. Subsets

           

    🔗 LeetCode Link

            
    // C++
vector> subsets(vector& nums) {
    vector> result;
    vector current;
    generateSubsets(nums, 0, current, result);
    return result;
}

void generateSubsets(const vector& nums, int index, vector& current, vector>& result) {
    result.push_back(current); // Add the current subset to the result

    for (int i = index; i < nums.size(); ++i) {
        current.push_back(nums[i]);  // Include the current element
        generateSubsets(nums, i + 1, current, result); // Recurse with the next element
        current.pop_back();  // Backtrack: remove the current element for other subsets
    }
}

// Java
public List> subsets(int[] nums) {
    List> result = new ArrayList<>();
    List currentSubset = new ArrayList<>();
    generateSubsets(nums, 0, currentSubset, result);
    return result;
}

private void generateSubsets(int[] nums, int index, List currentSubset, List> result) {
    result.add(new ArrayList<>(currentSubset)); // Add a copy of the current subset

    for (int i = index; i < nums.length; i++) {
        currentSubset.add(nums[i]);  // Include the current element
        generateSubsets(nums, i + 1, currentSubset, result); // Recurse with the next element
        currentSubset.remove(currentSubset.size() - 1); // Backtrack
    }
}
         
    10.      
  10.        

    10. Lowest Common Ancestor of a Binary Search Tree

           

    🔗 LeetCode Link

            
    // C++
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr) {
        return nullptr;
    }
    // If both p and q are smaller than root, LCA is in the left subtree
    if (p->val < root->val && q->val < root->val) {
        return lowestCommonAncestor(root->left, p, q);
    }
    // If both p and q are greater than root, LCA is in the right subtree
    else if (p->val > root->val && q->val > root->val) {
        return lowestCommonAncestor(root->right, p, q);
    }
    // Otherwise, root is the LCA (one is in left, one in right, or one is root itself)
    else {
        return root;
    }
}

// Java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { this.val = x; }
 * }
 */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }
    // If both p and q are smaller than root, LCA is in the left subtree
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    }
    // If both p and q are greater than root, LCA is in the right subtree
    else if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    // Otherwise, root is the LCA (one is in left, one in right, or one is root itself)
    else {
        return root;
    }
}
         
    11.    
 
Tags:

Post a Comment

Previous Post Next Post