# Interview Preparation Kit, Array

## Left rotation

• Thought: Rotate as intuition, but note that if index - rot_cnt (which is d) then the position should be size - (rot_cnt - index)
• Analysis:
• Time complexity: O(N)
• Space complexity: O(N)
// Complete the rotLeft function below.
vector<int> rotLeft(vector<int> a, int d)
{
int n = a.size();
vector<int>res(n, 0);

for(int i = 0; i < n; i++)
{
if(i - d < 0)
{
res[n + (i - d)] = a[i];
}
else
{
res[(i - d) % n] = a[i];
}
}
return res;
}


## Subset I

• Thought: There are up to 2^N possibilities, brute force will definitely failed. Since it counts up to 2^N
• Analysis:
• Time complexity O(N * 2 ^ N), where N is the cardinality of set, we check all 2 ^ N possibles and use bit manipulation (right shift up to length N in binary represenation).
• Space complexity: O(2 ^ N), store all the possible subsets.
class Solution
{
public:
vector<vector<int>> subsets(vector<int>& nums)
{
int n = nums.size();
int m = 1 << n, cnt = 0, i = 0;
vector<vector <int> > res(0, vector<int>());
vector<int> tmp;
while(--m)
{
cnt = 0;
i = m;
while(i > 0)
{
if(i & 1)
{
tmp.push_back(nums[nums.size() - cnt - 1]);
}
cnt++;
i >>= 1; //shift right to check the next occurance
}
res.push_back(tmp);
tmp.clear();
}
tmp.clear();
res.push_back(tmp);//including the empty one
return res;
}
};


## Minimum Swaps 2

• Thought: Draw the circular relation b/w the numbers according to this page

• Analysis:

• Time complexity: O(NlogN)
• Space complexity: O(N)
// Complete the minimumSwaps function below.
int dfs_circle(const vector<int>& arr_padded, int cur_pos, int arrow_cnt, int start_num, vector<bool>& visited)
{
visited[cur_pos] = true;// mark current node as traversed

cur_pos = arr_padded[cur_pos]; // move to the next one
if(visited[cur_pos] == false)
{
arrow_cnt = dfs_circle(arr_padded, cur_pos, arrow_cnt + 1, start_num, visited); // keep dfs-ing
}
return arrow_cnt;

}
int minimumSwaps(vector<int> arr)
{
int n = arr.size(), res = 0;

vector<bool> visited(n + 1, false);
bool finished_all = true;
for(int i = 1; i < n + 1;)
{
if(arr_padded[i] == i) // already in the right position, no need for dfs, to avoid stackoverflow
{
i++;
continue;
}
else
{
finished_all = true;
for(int j = 1; j < n + 1; j++)
{
if(visited[j] == false)
{
i = j;
finished_all = false;
break;
}
}

if(finished_all == false)
{