Scribd
Upload
17 views

Problem On Method

Questions

Uploaded by

vikramabhang
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
17 views

Problem On Method

Questions

Uploaded by

vikramabhang
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Problem: Trap Rain Water

Given an array height representing the elevation map where the width of each bar is 1, compute
how much water it can trap after raining.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation:
 The elevation map [0,1,0,2,1,0,1,3,2,1,2,1] is represented by vertical bars.
 After the rain, the amount of water trapped between the bars is 6 units.
Optimal Approach: Two-Pointer Technique
To solve this problem optimally, you can use a two-pointer technique. The idea is to maintain
two pointers (left and right), and use two variables (leftMax and rightMax) to keep track of the
maximum heights seen from the left and right sides respectively.

Explanation:
 Two Pointers (left and right): Start from both ends of the array.
 Track Maximum Heights (leftMax and rightMax): As you move the pointers inward,
keep track of the highest bar seen so far from the left and right.
 Calculate Water:
o If height[left] < height[right], the trapped water at left depends on leftMax. If
leftMax is greater than height[left], water can be trapped.
o Otherwise, calculate the trapped water using rightMax when height[right] is less
than or equal to height[left].
 Move Pointers: Depending on the comparison of heights at left and right, move the
corresponding pointer inward.
Time Complexity:
 The time complexity is O(n) where n is the length of the height array. This is because
each element is processed at most once.
Space Complexity:
 The space complexity is O(1) since only a few extra variables are used.
This approach is efficient and solves the problem in linear time.

Q2. Word Ladder


Problem:
Given two words (beginWord and endWord), and a dictionary, find the shortest transformation
sequence from beginWord to endWord such that only one letter can be changed at a time, and
each intermediate word must exist in the dictionary.

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output:
5

Explanation:
"hit" -> "hot" -> "dot" -> "dog" -> "cog" is a sequence of 5 words.

N-Queens Problem
Problem:
Place N queens on an N×N chessboard such that no two queens threaten each other. Return all
possible solutions.

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Q3. K-th Smallest Element in a BST


Problem:
Given a binary search tree, write a function to find the k-th smallest element in the tree.

You might also like