ASSIGNMENT-4

Divide and Conquer:

1) Longest Nice Substring:
Code:
class Solution {
public:
string longestNiceSubstring(string s) {
string output = "";
int count = 0;
for(int i = 0;i<s.length();i++){
int smallMask=0;
int largeMask = 0;
char ch = s[i];
int chint = 0;
if(ch>=65 && ch<=90){
chint = ch-'A';
largeMask = 1<<chint;
}
else{
chint = ch-'a';
smallMask = 1<<chint;
}
for(int j = i+1;j<s.length();j++){
ch = s[j];
if(ch>=65 && ch<=90){
chint = ch-'A';
largeMask |= 1<<chint;
}
else{
chint = ch-'a';
smallMask |= 1<<chint;
}
if((smallMask^largeMask) == 0){
if(count<j-i+1){
count = j-i+1;
string temp(s.begin()+i,s.begin()+j+1);
 output = temp;
}
}
}
}
return output;
}
};

Output:

2) Reverse Bits:
Code:
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t ans=0;
for (int i = 0; i < 32; i++) {
ans = ans<<1;
if(n&1){
ans=ans|1;
 }
n = n>>1;
}
return ans;
}
};
Output:

3) Number of 1 Bits:
Code:
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans=0;
while(n){
if(n&1){
ans++;
}
n=n>>1;
}
return ans;
}
 };

Output:

4) Maximum Subarray
Code:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxi=INT_MIN;
int n=nums.size();
int sum=0;
for(int i=0;i<n;i++){
sum+=nums[i];
maxi=max(maxi,sum);
if(sum<0) sum=0;

}
return maxi;
}
};
 Output:

5) Search a 2D Matrix II
Code:
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row=matrix.size();
int col=matrix[0].size();
int rowIndex=0;
int colIndex=col-1;
while(rowIndex<row && colIndex>=0){
int element=matrix[rowIndex][colIndex];
if(element==target){
return 1;
}
if(element<target){
rowIndex++;
}
if(element>target){
colIndex--;
}
 }
return 0;
}
};

Output:

6) Super Pow:
Code:
class Solution {
public:
const int MOD = 1337;

int pow(int a, int b) {

int result = 1;
a %= MOD;
for (int i = 0; i < b; i++) {
result = (result * a) % MOD;
}
return result;
}

int superPow(int a, vector<int>& b) {

int result = 1;
for (int i = b.size() - 1; i >= 0; i--) {
 result = (result * pow(a, b[i])) % MOD;
a = pow(a, 10);
}
return result;
}
};

Output:

7) Beautiful Array:
Code:
class Solution {
public:
static bool comp(const int &a, const int &b){
int mask = (a^b);
mask = mask & (-mask);
return a & mask;
}

vector<int> beautifulArray(int n) {
vector<int> answer;
while(n) answer.push_back(n--);
 sort(answer.begin(), answer.end(), comp);

return answer;
}
};

Output:

8) The Skyline Problem:

Code:
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<vector<int>> ans;
multiset<int> pq{0};

vector<pair<int, int>> points;

for(auto b: buildings){
points.push_back({b[0], -b[2]});
points.push_back({b[1], b[2]});
}

sort(points.begin(), points.end());
 int ongoingHeight = 0;

for(int i = 0; i < points.size(); i++){

int currentPoint = points[i].first;
int heightAtCurrentPoint = points[i].second;

if(heightAtCurrentPoint < 0){

pq.insert(-heightAtCurrentPoint);
} else {
pq.erase(pq.find(heightAtCurrentPoint));
}

// after inserting/removing heightAtI, if there's a change

auto pqTop = *pq.rbegin();
if(ongoingHeight != pqTop){
ongoingHeight = pqTop;
ans.push_back({currentPoint, ongoingHeight});
}
}

return ans;
}
};
Output:
9) Reverse Pairs:
Code:
class Solution {
private:
void merge(vector<int>& nums, int low, int mid, int high, int&
reversePairsCount){
int j = mid+1;
for(int i=low; i<=mid; i++){
while(j<=high && nums[i] > 2*(long long)nums[j]){
j++;
}
reversePairsCount += j-(mid+1);
}
int size = high-low+1;
vector<int> temp(size, 0);
int left = low, right = mid+1, k=0;
while(left<=mid && right<=high){
if(nums[left] < nums[right]){
temp[k++] = nums[left++];
}
else{
temp[k++] = nums[right++];
}
}
while(left<=mid){
temp[k++] = nums[left++];
}
while(right<=high){
temp[k++] = nums[right++];
}
int m=0;
for(int i=low; i<=high; i++){
nums[i] = temp[m++];
}
}
 void mergeSort(vector<int>& nums, int low, int high, int&
reversePairsCount){
if(low >= high){
return;
}
int mid = (low + high) >> 1;
mergeSort(nums, low, mid, reversePairsCount);
mergeSort(nums, mid+1, high, reversePairsCount);
merge(nums, low, mid, high, reversePairsCount);
}
public:
int reversePairs(vector<int>& nums) {
int reversePairsCount = 0;
mergeSort(nums, 0, nums.size()-1, reversePairsCount);
return reversePairsCount;
}
};

Output:
10) Longest Increasing Subsequence II
Code:
class Solution {
public:
vector<int>tree;
void update(int node,int st,int end,int i,int val){
if(st==end){
tree[node]=max(tree[node],val);
return;
}
int mid=(st+end)/2;
if(i<=mid){
update(node*2,st,mid,i,val);
}else{
update(node*2+1,mid+1,end,i,val);
}
tree[node]=max(tree[node*2],tree[node*2+1]);
}
int query(int node,int st,int end,int x,int y){
if(x>end || y<st) return -1e9;
if(st>=x && end<=y){
return tree[node];
}
int mid=(st+end)/2;
int left=query(2*node,st,mid,x,y);
int right=query(2*node+1,mid+1,end,x,y);
return max(left,right);
}
int lengthOfLIS(vector<int>& nums, int k) {
int n=nums.size();
if(n==1) return 1;
int m=*max_element(nums.begin(),nums.end());
tree.clear();
tree.resize(4*m+10);
for(int i=n-1;i>=0;i--){
int l=nums[i]+1,r=min(nums[i]+k,m);
 int x=query(1,0,m,l,r);
if(x==-1e9) x=0;
update(1,0,m,nums[i],x+1);
}
return tree[1];
}
};

Output: