After forming a first sacrificial gate stack over a portion of a first semiconductor fin located in a logic device region of a substrate, and a second sacrificial gate stack over a portion of a second semiconductor fin located in a memory device region of the substrate, in which each of the first sacrificial gate stack and the second sacrificial gate stack includes, from bottom to top, a tunneling oxide portion, a floating gate electrode, a control oxide portion, a gate conductor and a gate cap, an entirety of the first sacrificial gate stack is removed to provide a first gate cavity, and only the gate cap and the gate conductor are removed from the second sacrificial gate stack to provide a second gate cavity. Next, a high-k gate dielectric and a gate electrode are formed within each of the first gate cavity and the second gate cavity.