Note basic
• leetcode 136 - single number
Given a non-empty array of integers nums, every element appears twice except for one. Find that
single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = [1]
Output: 1
Constraints:
o 1 <= nums.length <= 3 * 104
o 3 * 104 <= nums[i] <= 3 * 104
o Each element in the array appears twice except for one element which appears only
once.
• static and dynamic allocation
• Kadanes algorithm -leetccode 53, subarray sum
Given an integer array nums, find the
subarray
with the largest sum, and return
its sum
.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints:
o 1 <= nums.length <= 105
o 104 <= nums[i] <= 104
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and
conquer approach, which is more subtle.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//kadane's algorithm
int currentSum = 0;
int maxSum = INT_MIN;
/* for (int start = 0; start < nums.size();start++){ */
for (int start:nums){
currentSum += start;
maxSum = max(currentSum,maxSum);
if(currentSum < 0){
currentSum = 0;
return maxSum;
};
• leetcode 169- Majority element
• class Solution {
• public:
• int majorityElement(vector<int>& nums) {
• //brute force approch : o(n2)
• /* int n = nums.size();
• for(int val : nums){
• int frequency = 0;
• for(int ele: nums){
• if(val == ele){
• frequency++;
• }
• }
• if( frequency > n/2){
• return val;
• }
• }
•
• return -1; */
• //sorting approch better than brute force : o(nlogn)
• /* int n = nums.size();
• sort(nums.begin(),nums.end());
• int fre = 1;
• int ans = nums[0];
• for(int i = 1; i<n; i++){
• if( nums[i] == nums[i-1]){
• fre++;
• }else{
• fre = 1;
• ans = nums[i];
• }
• if(fre > n/2){
• return ans;
• }
• }
• return ans; */
• //mores voting algorithm : o(n)
• int fre = 0;
• int ans = 0;
• for (int i =0; i<nums.size(); i++){
• if(fre ==0){
• ans = nums[i];
• } if(ans == nums[i]){
• fre++;
• }else{
• fre--;
• }
• }
• return ans;
• }
• };
• Leetcode 50 || Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Constraints:
o 100.0 < x < 100.0
o 231 <= n <= 2311
o n is an integer.
o Either x is not zero or n > 0.
o 104 <= xn <= 104
class Solution {
public:
double myPow(double x, int n) {
//corners (if unique input)
if(n==0) return 1.00;
if(x==0) return 0.00;
if(x == 1) return 1.00;
if(x == -1 && n%2 == 0) return 1.00;
if(x == -1 && n%2 != 0) return -1.00;
long binForm = n; //store power n into binForm
double ans = 1;
if(n < 0){ //if power is negative
binForm = -binForm; // make n into positive
x = 1/x; // if power is negative number become 1/x
while(binForm>0){
if(binForm % 2 == 1 ){ // reminder is reponsible for binary last digit is 1 or 0
ans *= x; // ans = ans * x where x is the number
x *= x; // x = x * x where x is multiply by the number
binForm /=2; // number is multiply so the power is devided by 2
return ans;
};
• 121. Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different
day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit,
return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
o 1 <= prices.length <= 105
o 0 <= prices[i] <= 104
class Solution {
public:
int maxProfit(vector<int>& prices) {
int bestBuy = prices[0]; // store first day as the best buy day
int maxProfit = 0;
for (int i = 1; i < prices.size(); i++){
if(prices[i] > bestBuy){ // compare bestBuy number with the i th day element
maxProfit = max(maxProfit,prices[i]-bestBuy);// find maximum between i'th day profit and
before profite
}
bestBuy = min(bestBuy,prices[i]); //find minimum between previous price and i'th day price
return maxProfit;
};
• Leetcode 11 | Container with Most Water || 2 pointer approch
• class Solution {
• public:
• int maxArea(vector<int>& height) {
• /* Brute force approch : O(n2) (Time Limit Exceeded 56 / 63 testcases passed
• because Constraints:
• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104 ) */
• /* int maxWater = 0;
• for(int i = 0; i < height.size(); i++){
• for(int j = i + 1; j < height.size(); j++){
• int heightWater = min(height[i], height[j]); // find minimum water height level from
seleted two line
• int width = j - i; // width is right line - first line
• int area = heightWater * width;
• maxWater = max(area, maxWater);
• }
• }
• return maxWater; */
•
• // 2 Pointer Approch : O(n)
• int maxWater = 0;
• int leftBar = 0;
• int rightBar = height.size() - 1;
• while(leftBar < rightBar){
• int heightofWater = min(height[leftBar],height[rightBar]);
• int width = rightBar - leftBar;
• int area = heightofWater * width;
• maxWater = max(maxWater,area);
• height[leftBar] < height[rightBar] ? leftBar++ : rightBar-- ; // tinary operator for if ccase
• }
• return maxWater;
• }
• };
11. Container With Most Water
Solved
Medium
Topics
Companies
Hint
You are given an integer array height of length n. There are n vertical lines drawn such that the two
endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the
most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
!https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/17/question_11.jpg
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max
area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
Constraints:
o n == height.length
o 2 <= n <= 105
o 0 <= height[i] <= 104
• https://brainstation.io/career-guides/software-engineer-interview-
questions?utm_source=chatgpt.com
